Dijkstra’s shortest path algorithm calculates the shortest distance between
vertices in a *weighted graph with non-negative edge weights*. This is
without a doubt one of the

*greatest hits*of algorithms with countless applications. Those wishing to excel in computer science should take extra car to ensure they fully understand this.

The algorithm as shown in the this section is a naive implementation. Each iteration of the main while loop requires a scan over all edges to find the one with the minimum distance. While this runtime isn’t horrible, it’s possible to do much better using the implementation in the next section.

## Asymptotic Complexity

$O(mn)$

## Pseudo Code

```
dijkstra:
G = input graph with distance of each vertex set to infinity
v = starting vertex
side effects: marks all vertices with the shortest distance from the starting
vertex
S = empty array
v.distance = 0
S.add(v)
while true:
u = find_min(G, S)
if u is NULL or u.distance == infinity:
break
S.add(u)
find_min:
G = input graph
S = array containing all conquered vertices
v = NULL
for each vertex in S:
for each edge in vertex:
if edge.head is contained in S:
continue
distance = edge.tail.distance + edge.weight
if distance < edge.head.distance
edge.head.distance = distance
if edge.head.distance < v.distance
v = edge.head
return v
```

## Source Code

Relevant Files:

Click here for build and run instructions