如何在此图上应用 Dijkstra 算法？
How to apply Dijktra algorithm on this graph?
如何在此图上应用 dijkstra 算法？
我一直在尝试，但我无法弄清楚它是怎么回事？
例如，如果我们要找到从 a 到 c 的最短路径，那么它不应该是 3，因为最短的路径是从 a 到 b (1) 然后 b 到 c (2)，所以总共 3重量。但是，答案显示 4 是直接从 a 到 c。
这里有什么帮助吗？
您以正常方式应用 Dijkstra 算法，从 a 到 c 的最短路径实际上是 3。但是，您应该阅读 Dijkstra 的 pseudocode 以了解 table.
首先，Dijkstra returns一个数组（或另一个数据结构，取决于实现，为了我们的目的，只是说它是一个数组）从一个给定顶点到所有顶点的所有最短路径在图中。在这种情况下，如果您想使用 Dijkstra 来确定从 a 到 c 的最短路径，您可以从 a 运行 它然后检查返回的数组中的路径至 c.
那个table就是从a开始计算最短路径的整个过程。它使用类似 this video 的符号，只是在视频中他们使用数字来标记下一次迭代，这里使用从优先级队列中取出的顶点的名称。在伪代码中，你有 u ← vertex in Q with min dist[u]。最左边的字母是 u。整行仅显示最佳值是否更改以及更改为什么。
例如你从 a 到 c 的路径：在第一次迭代中，我们从 a 开始寻找邻居。由于 a 的邻居是 c（长度为 4 的路径）、b（长度为 1）和 d（路径为 3），我们保存这些值（起始顶点为a，所以从a到a的路径自动为0并且e不是a的邻居，所以还没有到它的路径） .这是您 table 的第一行。对于第二次迭代，我们选择 b（查看伪代码原因）——这是第二行中的第一个字母。现在我们查看 b 的邻居并尝试查看是否可以改进我们在第一次迭代中标记的一些路径。正如您在图中看到的那样，我们直接从 a 找到 c 和 d 的更短路径（不要忘记 - 您需要对 [= 的路径求和10=] 到 b 和从 b 到给定的顶点）。 e 仍然没有找到，因为它也不是 b 的邻居。整个第二行显示了我们从优先级队列中选择 b 后的最佳路径。
我们继续，直到所有顶点都被访问并填充 table 中的所有行。第一个字母仍然是伪代码中的 u（从优先级队列中选择的顶点），该行的其余部分是路径在该迭代中的改进方式。如果你试图在你的图表上模仿 Dijkstra，你就会看到它。最后一行也是返回的最短路径数组。
关于您的评论（第 2 行，B 到 A 是 0，B 到 B 是 1，B 到 C 是 3。）- 这是不对的，因为您可以看到从 b 到c 是 2（并且没有办法从 b 到 a，所以距离将是无穷大）。但是，要看到您需要 b 中的 运行 Dijkstra 作为起始顶点。
如何在此图上应用 dijkstra 算法？ 我一直在尝试，但我无法弄清楚它是怎么回事？
例如，如果我们要找到从 a 到 c 的最短路径，那么它不应该是 3，因为最短的路径是从 a 到 b (1) 然后 b 到 c (2)，所以总共 3重量。但是，答案显示 4 是直接从 a 到 c。
这里有什么帮助吗？
您以正常方式应用 Dijkstra 算法，从 a 到 c 的最短路径实际上是 3。但是，您应该阅读 Dijkstra 的 pseudocode 以了解 table.
首先，Dijkstra returns一个数组（或另一个数据结构，取决于实现，为了我们的目的，只是说它是一个数组）从一个给定顶点到所有顶点的所有最短路径在图中。在这种情况下，如果您想使用 Dijkstra 来确定从 a 到 c 的最短路径，您可以从 a 运行 它然后检查返回的数组中的路径至 c.
那个table就是从a开始计算最短路径的整个过程。它使用类似 this video 的符号，只是在视频中他们使用数字来标记下一次迭代，这里使用从优先级队列中取出的顶点的名称。在伪代码中，你有 u ← vertex in Q with min dist[u]。最左边的字母是 u。整行仅显示最佳值是否更改以及更改为什么。
例如你从 a 到 c 的路径：在第一次迭代中，我们从 a 开始寻找邻居。由于 a 的邻居是 c（长度为 4 的路径）、b（长度为 1）和 d（路径为 3），我们保存这些值（起始顶点为a，所以从a到a的路径自动为0并且e不是a的邻居，所以还没有到它的路径） .这是您 table 的第一行。对于第二次迭代，我们选择 b（查看伪代码原因）——这是第二行中的第一个字母。现在我们查看 b 的邻居并尝试查看是否可以改进我们在第一次迭代中标记的一些路径。正如您在图中看到的那样，我们直接从 a 找到 c 和 d 的更短路径（不要忘记 - 您需要对 [= 的路径求和10=] 到 b 和从 b 到给定的顶点）。 e 仍然没有找到，因为它也不是 b 的邻居。整个第二行显示了我们从优先级队列中选择 b 后的最佳路径。
我们继续，直到所有顶点都被访问并填充 table 中的所有行。第一个字母仍然是伪代码中的 u（从优先级队列中选择的顶点），该行的其余部分是路径在该迭代中的改进方式。如果你试图在你的图表上模仿 Dijkstra，你就会看到它。最后一行也是返回的最短路径数组。
关于您的评论（第 2 行，B 到 A 是 0，B 到 B 是 1，B 到 C 是 3。）- 这是不对的，因为您可以看到从 b 到c 是 2（并且没有办法从 b 到 a，所以距离将是无穷大）。但是，要看到您需要 b 中的 运行 Dijkstra 作为起始顶点。