Here is an implementation of Dijkstra's single source shortest path algorithm in JavaScript. The shortestPath function takes three arguments: the adjacency matrix defining the graph, the number of vertices in the graph, and the starting vertex number. The adjacency matrix should be defined such that E[i][j] == Infinity means that there is no arc between vertex i and j, and E[i][j] == n means that there is an arc with weight n between i and j. The adjacency matrix can define a directed graph; the example one in the code is undirected though (since E[i][j] == E[j][i] for all i and j).
The function will return an object encapsulating the shortest path info for the given starting vertex. It has three properties: a pathLengths property, which is an array that gives the shortest path length from the starting vertex to each vertex i, predecessors, which is a predecessor list describing the spanning tree that defines the actual shortest paths from the starting vertex to each other vertex, and startVertex, the starting vertex the shortest path data is valid for. To get an actual list of vertices comprising the path to a given vertex, use the constructPath function. It takes the shortest path info object returned from shortestPath and the vertex you want to go to, and returns an array of vertices that comprise the path.
An example of this algorithm's use in SVG is given here.
October 21, 2004 ... updated December 13, 2004
