# Graph Theory/Weighted graphs and algorithms

Algorithm (Dijkstra's algorithm):

Let ${\displaystyle G=(E,V)}$ be a finite digraph with weight ${\displaystyle c:E\to \mathbb {R} }$. Fix a node ${\displaystyle x\in V}$. Then the following algorithm computes a shortest path from any node other than ${\displaystyle x}$ to ${\displaystyle x}$:

In C, the graph ${\displaystyle G}$ and the function ${\displaystyle c:E\to \mathbb {R} }$ shall be given by the nodes ${\displaystyle 0,\ldots ,n-1}$ (where ${\displaystyle n=|V|}$ and ${\displaystyle x=0}$) and a weight function double long weight(int source, int target) which is ${\displaystyle -1}$ whenever source and target are not incident.

 1 boolean nextStep[n];
2 int nextStepLength;
3
4 nextStepLength = 1;
5 for(k=0;k<n;k++) {
6     nextStep[k] = k;
7 }
8
9 int step;
10 int vNo;
11 for(step=0;step<n;step++) {
12     for(vNo = 0; vNo < nextStepLength; vNo++) {
13
14     }
15 }