A shortest path (if it exists) can always be achieved cycle free:
Why the funny name for a move that "tightens up"
the distance to v?
It is historical, coming from "relaxing" the triangle
constraint on the distance between u and
v.
Relax(u, v, w)
if v.d > u.d + w(u, v)
v.d = u.d + w(u, v)
v.pred = u
Discovered by Edsger Dijkstra.
1 function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph: // Initialization
6 dist[v] = INFINITY // Unknown distance from source to v
7 prev[v] = UNDEFINED // Previous node in optimal path from source
8 add v to Q // All nodes initially in Q (unvisited nodes)
9
10 dist[source] = 0 // Distance from source to source
11
12 while Q is not empty:
13 u = vertex in Q with min dist[u] // Node with the least distance
14 // will be selected first
15 remove u from Q
16
17 for each neighbor v of u: // where v is still in Q.
18 alt = dist[u] + length(u, v)
19 if alt < dist[v]: // A shorter path to v has been found
20 dist[v] = alt
21 prev[v] = u
22
23 return dist[], prev[]