vlambda博客
学习文章列表

一.题目描述

此处的最短路径为单源最短路径问题

(参考教学：屈婉玲《算法设计》)

给定带权有向网络G=(V,E,W)，每条边e=<i,j>的权w(e)为非负数，表示从i到j的距离。求从源点s出发到达其他结点的最短路径。

输入：有向图G=(V,E,W)，V={1,2,3...n},s=1

输出：从s到每个顶点的最短路径

二.Dijkstra算法

求单源最短路径问题一般用到Dijkstra算法，Dijkstra算法是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

Dijkstra算法有关概念

初始：S={s},S=V时算法结束

从s到u相对于S的最短路径：从s到u且经过S中顶点的最短路径

dist[u]：从s到u相对于S最短路径的长度

short[u]：从s到u的最短路径的长度

Dijkstra算法设计思想

输入：有向图G=(V,E,W)，V={1,2,3...n},s=1

输出：从s到每个顶点的最短路径

1. 初始化S={1}

2. 对于i属于[V-S]，计算1到i相对于S的最短路径，长度dist[i]

3. 选择[V-S]中dist值最小的j，将j加入S，修改V-S中顶点的dist值

4. 继续上述过程，直到S=V为止

三.Dijkstra算法伪代码

算法：Dijkstra
  1.S <—— {s}
  2.dist[]
  3.for i ∊ V - {s} do
  4.    dist[i] <—— w(s,i) # 若s到i没边，则w(s,i)= ∞
  5.while V - S ≠ Ø do
  6.    从V-S取相对于S的最短路径顶点j
  7.    S <—— S ∪ {j}
  8.    for i ∊ V-S do
  9.        if dist[j]+w[j,i] < dist[i]
  10.       then dist[i] <—— dist[j] + w[j,i]

END

往期回顾