Graph Theory/Weighted graphs and algorithms

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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++) {