Content deleted Content added
m Archiving 2 discussion(s) to Talk:Dijkstra's algorithm/Archive 2) (bot |
Salix alba (talk | contribs) →Pseudocode improvement: test for infinity not on CRLS source. |
||
Line 45:
In first pseudocode block, on line 15, dist[u] is checked for not being INFINITY. But if it is INFINITY at this point, the code will continue useless looping, because all remaining vertices will also have dist[u]=INFINITY and not influence the result. Maybe move the INFINITY check to line 11 and break out of while block, it would be more human readable too I think --[[User:Shrddr|Shrddr]] ([[User talk:Shrddr|talk]]) 20:44, 20 August 2022 (UTC)
We should stick to sources rather than commit [[WP:OR]]. CLRS has
<pre>
DIJKSTRA(G, w, s) // Graph G, weights w, source vertex s
1 INITIALIZE-SINGLE-SOURCE(G, s) // lines 3-5 of our algorithm
2 S = 0 // empty set
3 Q = G.V // line 6
4 while Q non empty
5 u = EXTRACT-MIN(Q) // line 10, 11
6 S = S union {u}
7 for each vertex v in G:Adj(u) // slightly different to ours
8 RELAX(u,v,w)
</pre>
where RELAX is
<pre>
RELAX(u, v, w)
1 if v.dist > u.dist + w(u, v)
2 v.dist = u.dist + w(u, v)
3 v.prev = u
</pre>
There is nothing in this algorithm with a test of u.dist being infinity. So I think its safe to remove the condition entirely. --[[User:Salix alba|Salix alba]] ([[User talk:Salix alba|talk]]): 10:44, 21 August 2022 (UTC)
| |||