411 REFERENCE · Wikibooks
Graph Theory/Weighted graphs and algorithms
Reference material by Wikibooks contributors. This retains its source identity and is not 411 news reporting.
Dijkstra's algorithm Let be a finite digraph with weight . Fix a node . Then the following algorithm computes a shortest path from any node other than to :
In C, the graph and the function shall be given by the nodes (where and ) and a weight function double long weight(int source, int target) which is whenever source and target are not incident.
boolean nextStep[n];
int nextStepLength;
nextStepLength = 1;
for(k=0;k<n;k++) {
nextStep[k] = k;
}
int step;
int vNo;
for(step=0;step<n;step++) {
for(vNo = 0; vNo < nextStepLength; vNo++) {
}
}