C++ :: Dijkstra's Algorithm - Find Shortest Path In A Dense Graph

Code that finds a shortest path in a dense graph, using Dijkstra's algorithm in the simple array version. You write a function

struct listnode shortest path(int n, int s, int t, int *dist)
with
struct listnode f struct listnode * next; int vertexnumber; g ;

Being used to return the list of vertices on the shortest path. Your function has the following arguments:

- n: the number of vertices of the graph,
- s: the start vertex,
- t: the target vertex
- dist: the matrix of edgelengths.

The vertices are numbered from 0 to n -1, so s and t are numbers in that range. dist is a pointer to the n * n matrix of edgelengths; vertices which are not connected will be joined by an edge of length 9999. To access the array element dist[i][j], we can use *(dist + i*n + j). Your function should return the list of vertices on the shortest path from s to t, starting with s and ending with t.