| Dijkstra(G,s): | ||
| 1 | for each vertex u ∈ G.V - {s} | |
| 2 | u.d = ∞ | |
| 3 | u.pred = null | |
| 4 | u.done = false | |
| 5 | u.timesRelaxed = 0 | |
| 6 | s.d = 0 | |
| 7 | Q = G.V | |
| 8 | while Q ≠ ∅ | |
| 9 | u = Q.extractMin() | |
| 10 | u.done = true | |
| 11 | for each v ∈ G.Adj[u] | |
| 12 | Relax(u,v) | |
| Relax(G,u,v): | ||
| 1 | if u.d + G.edge(u,v).w < v.d | |
| 2 | v.d = u.d + G.edge(u,v).w | |
| 3 | v.pred = u | |
| 4 | v.timesRelaxed += 1 | |
✎★G: |
|
★Q: |
Create a graph where a vertex gets relaxed at least 5 times.