Content deleted Content added
→Optimality for comparison-sorting by distance: but with variable edge weights |
|||
Line 108:
The base case is when there is just one visited node, {{mono|source}}. Its distance is defined to be zero, which is the shortest distance, since negative weights are not allowed. Hence, the hypothesis holds.
===
Assuming that the hypothesis holds for <math>k</math> visited nodes, to show it holds for <math>k+1</math> nodes, let {{mono|u}} be the next visited node, i.e. the node with minimum {{code|dist[u]}}. The claim is that {{code|dist[u]}} is the shortest distance from {{mono|source}} to {{mono|u}}.
| |||