最短路径(Dijkstra算法)

时间:2023-03-09 19:41:25
最短路径(Dijkstra算法)

算法局限性:边的权值不能为负。

需要两个辅助数组dist[],path[],分别记录起点到各点的最短距离和最短路径

算法步骤:
  1.根据起点v0初始化dist[]和path[]数组。

  2.在剩下的点中找出最短边。

  3.修改dist和path数组,重复步骤2,直到所有点都访问完。

最短路径(Dijkstra算法)

dist和path数组变化过程:(1号点为起点)

1.初始化时,dist[i]:分别是各点i到1号点的权值;path[i]:若i可达到1号点,值为1,否则为-1。

2.根据dist数组在剩下的点中寻找最短边,假设得到1->2是最短,重新设置dist和path数组,如果以1->2为起点到其余未访问过的点的距离小于以1为起点到其余未访问过的点的距离,就将dist[i]设置为新的以1->2为起点的权值,path[i]:同步骤1,若可达设置成2,否则不变。

3.再根据dist数组在剩下的点中寻找最短边......直到执行n-1次为止。