⑦ ABEFCD 长度为14；
⑧ ABCD 长度为12； ⑨ A对BC于F大E规D 模长复度杂为赋17权图，这种方法显然是不现实的， 所以也，不A到易D计的算最机短上通实路现是。A需F要CD寻，找A合到适D的的求距解离算为法3。。
二、Dijkstra算法
问题：从某个顶点出发，求到达各个顶点的最短路径。
对于简单图，当e=(vi,vj)(或e=<vi,vj>)时，也把w(e)记做 wij。
v3
5 e4
v4
3 e3
e2 8
v1
e1
6
v2
二、边权矩阵
设赋权图G=<V,E,w>, V={v1,v2,…,vn}
令aij为：
aij
wij (vi, vj)E（ <vi, vj>E ） (vi, vj)E （<vi, vj>E ）
转②； ⑤ 输出u到其它各个结点的最短通路的长度L(v)。
二、Dijkstra算法（续）
例 对于赋权图G1，求其中结点v1到各结点的最短通路？ 解 根据Dijkstra算法步骤，可得如下运算过程：
从上可知，结点v1到结点v2的最短通路为v1v2，距离为1； 结点v1到结点v3的最短通路为v1v2v3，距离为3；结点v1到 结点v4的最短通路为v1v2v3v5v4，距离为7；结点v1到结点 v5的最短通路为v1v2v3v5，距离为4；结点v1到结点v6的最 短通路为v1v2v3v5v4v6，距离为9。
算法核心：结点u到结点集V 的距离为：
d(u, V ) = minvV {d(u, v)} 等价于 d(u, V ) = min vV，xV {d(u, v) + w(v, x)}
Dijkstra 算法
基本符号： L表示从结点u到各个结点的通路的长度的当前最小值；
S表示已求得最短通路的结点集合。
并规定wii=0,
则称(aij)n╳n为G的权矩阵,记作W(G)。
例：
v3
5
v4
3 8
v1
6
v2
0 6
W
(G)
3
0
8 0
5
0
8.2.2 最短通路问题
一、最短通路问题
设G=<V,E,w>是n阶简单赋权图(有向或无向) 通路(回路)的长度：通路(回路)上各边的长度之
和；
u到v的最短通路：从u到v的所有通路中具有最 小长度的通路。
从图G知，A到D的所有简单通路有：
① AFED 长度为6；
枚举法
② AFEBCD 长度为13； ③ AFCD 长度为3；
（或穷举 法）
④ A通FC过B列E举D 出长所度有为简14单；通路及其长度，然后从中选择具有
⑤ A最D小长长度度为的1通0；路，得到问题的解。
⑥ ABED 长度为13；
u到v的距离：u到v的最短通路的长度，记为 d(u,v)。
最短通路问题就是在赋权图中寻找一个结点到 另一个结点的具有最小长度的通路。
一、 最短通路问题（续）
例如，图G是一个描述城市A、B、C、D、E和F的公路交通图，图 中的每一条边的权对应于各城市之间公路的长度。任意两个城 市之间可能有多条公路，求出长度最小的公路具有实际的意义 。这就对应于赋权图的最短通路问题。
二、Dijkstra算法（续）
Dijkstra算法步骤如下： ① 初始化：u = v1；L(u) = 0；L(vi) = （i = 2, 3, …, n）
；S = ； ② 如果|S| = n，转⑤； ③ 从VS中选取具有最小值L(v)的v，令S = S {v}； ④ 对于所有xVS，令L(x) = min {L(x)，L(v)+ w(v, x)}；
离散数学
第4篇 图论基础
§8.2 赋权图
赋权图
权矩阵
最短通路问题
求解最短路径问题的Dijkstra 算法 最短路径问题的应用
8.2.1 赋权图的定义
一、赋权图
对图G=<V,E>(有向或无向)的每条边e都附加一个实数w(e)，
将w(e)称为e的权，或者e的长度， 将G称为赋权图或带权图，记做G=<V,E,w>， 其中的w：ER，称为图G的权函数。
三、最短通路问题的应用
作业
P336 第27大题