Graph Theory/Weighted graphs and algorithms
Algorithm (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++) {
}
}