对于n车站，给出了一个n*n矩阵，表示从车站到(i,j <= n)的直接行程时间。AA[i][j]ij
在车站之间旅行的人总是寻求最少的时间。给定两个站号a，b如何计算它们之间的最短旅行时间？
这个问题可以在不使用图论的情况下解决，即仅通过矩阵 A 来解决吗？
问问题
1873 次
2 回答
5
你确实需要图论来解决它——更具体地说，你需要Dijkstra 的算法。将图表示为矩阵既不是该算法的优点也不是缺点。
但请注意，Dijkstra 算法要求所有距离都是非负的。如果由于某种原因矩阵中有负“距离”，则必须改用较慢的Bellman-Ford 算法。
（如果您真的热衷于使用矩阵运算并且不介意它会非常慢，您可以使用基于非常简单的矩阵运算的Floyd-Warshall 算法来计算所有对之间的最短路径站（大量过度杀伤），然后选择您感兴趣的对...）
于 2012-08-06T21:15:20.217 回答
-4
这看起来与 NP 难题的旅行商问题惊人地相似。
于 2012-08-06T21:11:25.533 回答