# Dijkstra's Shortest Path (Naive)

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

while true:
u = find_min(G, S)
if u is NULL or u.distance == infinity:
break

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