Ok, first off, the following pseudo code is only one implementation of Dijkstra's algorithm (a.k.a. the shortest path first algorithm.) *Look it up on google.
A few things to realize:
Quick version: Think of a number of cities on a map and the distances between them. *Dijkstra's algorithm starts at one of the cities and finds the shortest distances to all the other cities on the map from that starting point. *When I describe the algorithm, I will be using the term 'graph' instead of map, and 'node' or 'vertex' instead of cities, as this is a graphing problem (the graph data structure being a data structure that's more generalized than a tree.) *I will also be using the term 'arc' to mean a path between two vertices.
G is the graph, which also has the sets V (the set of vertices on the graph) and E (which is the set of arcs/paths between the vertices.)
S is the set of vertices for which we've already found the shortest path to.
P is an array of vertices and describes the various paths. *Given P[t]=j, j is the vertex just before t in the shortest path to t (if you can't understand it now, hopefully it'll be more clear in the pseudo-code.)
D is also an array of vertices. *Given D[t]=x, it takes x number of units to go from vertex 1 (the starting vertex) to vertex t.
C is a matrix (those rectangular thingies with numbers in them, but you do not need to know matrix math or linear algebra to do this problem.) *More specifically, it is a cost matrix. *The number in column t and row j represents the distance (a.k.a. cost, weight) to go from vertex i to j. *The easiest way to think of this is as a two dimensional array. *Column t and row j would then be represented by C[t][j]. *If there is no arc between two points, the distance between them is infinite.
In my pseudo code, I assume vertices are number from 1 to n, and 1 is the starting point.
Code:
shortest(Graph G, matrix C)
* S={1} // S initially has 1 in it
* for 1 to n in i do
* * *P[i]=1
* * *D[i]=C[1][i]
* for 1 to n-1 in i do
* * *Let w be D[t] such that D[t]<D[x] for every x in V - S
* * *S=Union(S, w)
* * *for each v such that v is adjacent to i do
* * * * if D[v]>D[w]+C[w][v]
* * * * * *P[v]=w
* * * * * *D[v]=D[w]+C[w][v]
Posting Permissions
Reply With Quote
Bookmarks