algorithm - 探索某些点的最短路径是什么

Question

图中有 N 个点，每个点都有一条到其他 (N-1) 个点的路径，并带有成本(例如，成本是直线距离或曼哈顿距离)。

对于任意点A、B、C，有两个约束条件:

成本(A->B)<=成本(A->C)+成本(C->B)

成本(A->B)==成本(B->A)

现在，我要做的是找到探索图中所有点的最短路径。方法是什么？或者没有解决这个问题的推进方法。

我有一个想法，假设A是起点，我们试着找到离A最近的点(假设是B)，然后我移动到B点。我试着找到离B最近的点(现在 A 被删除)再次，直到我探索所有点。

Answer 1

听起来像 Dijkstra's algorithm.

总结链接:

Start at an arbitrary source node. 
Set the distance between this node and all other nodes = +Infinity
Set the distance between this node and itself to, well, 0 :)
Iterate:
    Mark this node as 'visited'
    Find the distance between this node and its directly connected neighbors
    Update their distances if smaller 
    Go to the next unvisited neighbor which has the smallest distance from the source
     If no neighbors are unvisited, go back a step until you can find an unvisited neighbor. 
     If all neighbors of all nodes are visited, terminate.  

现在您有一个完全填充的表格，其中包含从源到每个节点的距离。选择最小值以找到最佳路径。另请注意，使用完全连接的图遵循此算法也会为您提供最小生成树，我相信，因为它始终会选择两个节点之间的最小距离，而不会重复任何节点。