0

我正在尝试学习更多关于图形和 Dijkstra 算法的东西，所以我有一个随机生成加权无向图的函数，保存在这样的文件中：

numbers_of_vertices number_of_nodes
node_a node_b distance_from_a_to_b
etc.

然后我运行 Dijkstra 输出从节点 0 到所有其他节点的距离，但有时从节点 0 到其他节点的距离为 0，这意味着从节点 0 到该节点没有连接？
另外我还有一个问题，Dijkstra 的作品是什么样的图表？>br> 感谢您的帮助！

4

1 回答 1

1

Dijkstra 算法是 BFS 遍历的一种变体。不同的是，它每次都利用最小堆遍历到最近的节点。

您的随机生成加权无向图的函数不应创建 node_a 和 node_b 距离为 0 的节点对。这意味着节点位于相同的确切位置 - 因此，无需遍历。

Dijkstra 的算法适用于任何具有起始和结束条件的加权图（仅具有正权重）。

这是解释算法的 10 分钟视频： https ://www.youtube.com/watch?v=pVfj6mxhdMw

于 2020-11-10T03:14:33.693 回答