jig*_*mnc -1 algorithm graph path matrix shortest
对于n站点,给出n*n矩阵A,其A[i][j]表示从站i到j(i,j <= n)的直接旅程的时间.
n
n*n
A
A[i][j]
i
j
在车站之间旅行的人总是寻求最少的时间.给定两个站号a,b如何计算它们之间的最短旅行时间？
a
b
没有使用图论可以解决这个问题,即仅仅通过矩阵A？
Aas*_*set 5
你需要图论来解决它 - 更具体地说,你需要Dijkstra的算法.将图表表示为矩阵既不是该算法的优点也不是缺点.
但请注意,Dijkstra的算法要求所有距离都是非负的.如果由于某种原因,矩阵中的"距离"为负,则必须使用较慢的Bellman-Ford算法.
(如果你真的热衷于使用矩阵运算并且不介意它会非常慢,你可以使用Floyd-Warshall算法,它基于非常简单的矩阵运算,来计算所有对之间的最短路径.站(大规模矫枉过正),然后挑选你感兴趣的那对...)
归档时间：
13 年，5 月 前
查看次数：
1544 次
最近记录：