Gra*_*ton 2 algorithm graph shortest-path data-structures
我有一个互连边缘列表(E),如何找到从一个顶点连接到另一个顶点的最短路径？
E
我正在考虑使用最低共同的祖先,但边缘没有明确定义的根,所以我认为解决方案不起作用.
最短路径由遍历的最小顶点数定义.
注意:可能存在连接两个顶点的多路径,因此显然广度优先搜索将不起作用
mon*_*ksy 9
Dijkstra的算法将为您完成此任务.
Art*_*ius 8
我不确定你是否需要在每对节点之间或两个特定节点之间的路径.既然某人已经给出了解决前者的答案,我会解释后者.
如果您没有关于图形的任何先验知识(如果您这样做,您可以使用基于启发式的搜索,例如A*),那么您应该使用广度优先搜索.
归档时间：
16 年，4 月 前
查看次数：
13279 次
最近记录：
14 年 前