Dijkstra 最短路径计算器

Dijkstra 算法可以在边权不为负的图中，求出从一个节点到其他所有节点的最短路径——它是路线规划、网络路由和许多教材习题的基础。把边按列表输入，选择起点（也可以选终点），这个计算器就会给出所有最短距离和路径，以及一张分步表格，像手工推演那样显示每一步访问了哪个节点、更新了哪些距离。

使用方法

1. 每行输入一条边：起点、终点和权重（A B 4）。
2. 单向边请勾选“有向”，双向边则不勾选。
3. 输入起始节点，以及可选的终止节点。
4. 查看距离与路径、所有节点的表格，以及各个步骤。

计算公式

重复：访问未访问节点中 d(u) 最小的 u · 对每条 u → v 的边（权重 w）：若 d(u) + w < d(v)，则令 d(v) = d(u) + w，prev(v) = u

除起点（0）外，所有距离初始为 ∞。节点一旦被访问，其距离就是最终的，而这只有在没有负权时才能保证——因此负权会被拒绝（Bellman–Ford 可以处理）。路径通过沿 prev 回溯到起点来还原。并列时先列出的节点优先。允许平行边，取较小的那条。

示例

示例是《Introduction to Algorithms》（CLRS）图 24.6 中的有向图。从 s 出发，访问顺序是 s（0）、y（5）、z（7）、t（8）、x（9）。到 x 的最短路线是 s → y → t → x，长度 9（5 + 3 + 1）。看起来直达的 s → t 边（10）输给了 s → y → t（8）。