为什么在 dijkstra 最短路径算法中，较晚确定的节点总是比较早确定的节点具有更长的最短距离
why in dijkstra shortest path algorithm, later determined nodes always have longer shortest distances than earlier determined nodes
我了解在每一步中，都会将一个新节点从未探索集移动到已探索集。这个节点 u 是通过最小化 d(s,v) + l(v,u) 来确定的，其中 v 是探索集中的一个节点。我理解 d(s,u) > d(s,v) 但不明白为什么 d(s,u) 大于探索集中任何 v_i 的 d(s,v_i) .这里的s代表源，d(s,u)是s到u的最短距离。谢谢
您看过 Dijkstra 的许多 YouTube 演示吗？
这个animation挺好的
如果对于任何 v_i，d(s,u) < d(s,v_i)，那么会先添加 v_i，因为您总是选择可实现的最小距离.
but don't understand why d(s,u) is larger than d(s,v_i) of any v_i in
explored set
这是归纳法属性。
基础：d(s,s) = 0，对于所有其他节点，d(s,u) >= 0
假设，在第 i 步，对于每个 u 探索的，v 未探索的，d(s,u) <= d(s,v).
让我们看一下步骤i+1，让x成为这一步中选择的节点。
根据归纳假设，对于探索中的每个 u，d(s,u) <= d(s,x)。对于未探索的每个其他节点 v - 如果在此步骤中未修改 d(s,v)，我们将通过第 i 步的归纳假设完成，并且由于 d(s,x) 是未探索的最小，d(s,x) <= d(s,v) 也是如此。
如果 d(s,v) 被修改，则 d(s,v) = d(s,x) + l(x,v) >= d(s,x)，因此 d(s,u) <= d(s,x) <= d(s,v)。
并且在任何情况下，在步骤 i+1 之后，对于 explored_i U {x} = explored_{i+1} 中的每个 u 和 unexplored_i \ {x} = unexplored_{i+1} 中的每个 v，d(s,u) <= d(s,v)。
QED.
我了解在每一步中，都会将一个新节点从未探索集移动到已探索集。这个节点 u 是通过最小化 d(s,v) + l(v,u) 来确定的，其中 v 是探索集中的一个节点。我理解 d(s,u) > d(s,v) 但不明白为什么 d(s,u) 大于探索集中任何 v_i 的 d(s,v_i) .这里的s代表源，d(s,u)是s到u的最短距离。谢谢
您看过 Dijkstra 的许多 YouTube 演示吗？ 这个animation挺好的
如果对于任何 v_i，d(s,u) < d(s,v_i)，那么会先添加 v_i，因为您总是选择可实现的最小距离.
but don't understand why d(s,u) is larger than d(s,v_i) of any v_i in explored set
这是归纳法属性。
基础：d(s,s) = 0，对于所有其他节点，d(s,u) >= 0
假设，在第 i 步，对于每个 u 探索的，v 未探索的，d(s,u) <= d(s,v).
让我们看一下步骤i+1，让x成为这一步中选择的节点。
根据归纳假设，对于探索中的每个 u，d(s,u) <= d(s,x)。对于未探索的每个其他节点 v - 如果在此步骤中未修改 d(s,v)，我们将通过第 i 步的归纳假设完成，并且由于 d(s,x) 是未探索的最小，d(s,x) <= d(s,v) 也是如此。
如果 d(s,v) 被修改，则 d(s,v) = d(s,x) + l(x,v) >= d(s,x)，因此 d(s,u) <= d(s,x) <= d(s,v)。
并且在任何情况下，在步骤 i+1 之后，对于 explored_i U {x} = explored_{i+1} 中的每个 u 和 unexplored_i \ {x} = unexplored_{i+1} 中的每个 v，d(s,u) <= d(s,v)。
QED.