# 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.

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

}
}