Q

跨多个矩阵的节点之间的最短路径

2017-02-20 78 views 0 likes

0

假设我有每行火车站的矩阵。行和列表示在该列车行中存在的车站。有没有办法找到各站之间的最短路径，包括那些使用火车线路之间的最短路径？我不能把它们全部放在一张图中，因为一些“边缘”具有不同的价值（例如，如果参数是成本，采取更便宜的路线将花费不同于其他列车路线）。跨多个矩阵的节点之间的最短路径

2017-02-20 noobalert

A

回答

1

使用Dijkstra算法：https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

它用遍了从视频游戏到(A*)dynamic routing protocols。

A *的相当不错的介绍：http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

2017-02-20 02:02:09 user1529891

+0

感谢您的快速评论！即使在多个图表上它也能工作吗？ – noobalert

+0

啊，我的不好。我想象一张表来表示顶点和边缘。我几乎忘了，如果我使用图形来代替，则两个顶点之间可能有两条边。无论如何，感谢您的时间和链接！我将从选择使用哪种算法开始。 – noobalert

相关问题