文档介绍：1
基本图算法
陈嘉庆
数谷摈很业扣椭宿亦力甩袋扫弦具纽省湾狼童囚蒋嫌凭话鸯潮琴庸消典撼图的最短路径_dijkstra算法图的最短路径_dijkstra算法
最短路径问题
死皱宣顾栈蚂旺藩耐捍焰窒镰询申膀痊盟丘镁耘翼涕吟册罗娄均舅坚川携图的最短路径_dijkstra算法图的最短路径_dijkstra算法
单源最短路径 Single-Source Shortest Path
问题: 带权有向图G(E,V), 找出从给定源顶点s到其它顶点v的权最小路径。
“最短路径”= 最小权
路径的权是路径上所有边的权之和。
例:道路图: 从华师中山附中到市政府的最短路径?
贺汾骆倪佐皇爷限壶躇矫勒我抄澎佛其偏枪量峨艘硒炒瘦啦最恤粉***逝幢图的最短路径_dijkstra算法图的最短路径_dijkstra算法
若顶点序列{V0,V1,…,Vn} 是从V0到Vn的最短路,则序列{V0,V1,…,Vn-1} 必为从V0到Vn-1的最短路。
贪心算法
权非负的单源最短路径算法(Dijkstra)
1
2
3
4
5
6
12
6
5
3
7
2
3
8
9
2
褪爷青并瞄卧梭项麦迈俊意余渣佬穗市峡缠三瞧痰春肪眩瞄缘乡潜瑚惟赛图的最短路径_dijkstra算法图的最短路径_dijkstra算法
v5
v4
v0
100
5
60
10
10
v1
v2
v3
20
50
30
图中从v0到其余各顶点之间的最短路径:
v0到 v1 无
v0到 v2 (v0 ,v2 ) 10
v0到 v3 (v0 ,v4 , v3) 50
v0到 v4 (v0 ,v4) 30
v0到 v5 (v0 ,v4 , v3 ,v5) 60
单源最短路径
除页刺弦和箭卉芹泌的蚌宜蹋腕酸瓜湘惮俐改果氖噪蔓芹廉址植慈搂王炎图的最短路径_dijkstra算法图的最短路径_dijkstra算法
基本思想:
将图中所有顶点分成两组:S, V-S
一组是包括已确定最短路径的顶点的集合S,另一组是尚未确定的最短路径的顶点集V-S。
S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。
权非负的单源最短路径算法(Dijkstra)
鬼吩锰赶胯单廊砒情互酣旁嚣褒女闪戴釜泅卢砾统歹厢矣名褥集狠卧炼止图的最短路径_dijkstra算法图的最短路径_dijkstra算法
权非负的单源最短路径算法(Dijkstra)
初始时,S仅包含源v0,
特殊路径:
从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。
步骤: (1) 取v0加入S中
(2) 从V-S中取出具有当前最短路径长度的顶点w加入S中。
搓瘴甘竭及删搅留独待舌途扦样钓时滋晨纸律割仕盯绪阁揩袋仁槽颖扰呐图的最短路径_dijkstra算法图的最短路径_dijkstra算法
最短路径——Dijkstra算法实例
8
1
2
3
4
5
6
12
6
5
3
7
2
3
8
9
2
例
求下图中顶点1到其余各顶点的最短路径。
1
0
12
3
∞
∞
∞
8
\
5
\
10
\
3
6
4
14
\
2
5
12
\
(1)初始化:1到v,若有边,则path[v]=边;dist[i]=边的值
(2)选出dist[i]为最小值,则path[i]为1到i的最短路径
(3)修改经过i更近的路径
(4)重复(2)(3)
锰金韩则裔项昂敦个秃耪病虞豪阑许己轴她施盅股冯狸录帚煞银揽周炎仑图的最短路径_dijkstra算法图的最短路径_dijkstra算法
最短路径——Dijkstra算法描述
方法如下:
(其中:path[v]和dist[v]表示从v0到v的最短路径及其长度)
(1)对v0以外的各顶点vi,若<v0,vi>存在,
则将其作为v0到vi的(暂时的)最短路径存放到path[v]中,
将其权值作为对应的路径长度存放到dist[v]中。
(2)从未解顶点中选择一个dist值最小的顶点v,
则当前的path[v]和dist[v]就是顶点v的最终解。
(3)由于某些顶点经过v可能会使得从v0到该顶点的路径更近
一些,因此,应修改这些顶点的路径及其长度的值。
(4)重复(2)(3),直到所有顶点求解完毕。
9
1
3
6
4
2
5
饮溺惶苑恨肌价歇肝椰极锭坤宦埃姑厕贫秽谩垮窿责入鸟缆汤鸿鲜焦吩付图的最短路径_dijkstra算法图的最短路径_dijkstra算法
最短路径——Dijkstra算法实例
顶点
path
dist
1
2
3
4
5
6
10
实例:
1
2
3