# Graph Theory/Weighted graphs and algorithms

Jump to navigation
Jump to search

This page was last edited 32 months ago, and may be abandonedThis page has not been edited since 9 September 2018, but other pages in this book might have been. Check out related changes to see what the state of this book is. You can help by editing and updating this book. Remove {{under construction}} from this page if it is not being actively edited. Ask for help at WB:PROJECTS. |

**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++) {
}
}
```