已知有向图G如下所示,根据迪杰斯特拉算法求顶点v0到其他顶点的最短距离。(给出求解过程)
贪心,用每一轮的最短路来进行更新
111
1
07475
02413
02431
0->1
12
0->4->1
7
0->2
4
0->3
9
0->2->3
8
0->4->3
0->4
5
4577
02413,02431
v0到其他顶点
终点
从v0到各终点的d值和最短路径的求解过程
i=1
i=2
i=3
i=4
v1
12 (v0,v1)
7 (v0,v4,v1)
v2
4 (v0,v2)
v3
9 (v0,v3)
8 (v0,v2,v3)
7 (v0,v4,v3)
v4
5 (v0,v4)
vj
s
{v0,v2}
{v0,v4}
{v0,v4,v1}
{v0,v4,v3}
v0,v2,v4,v1,v3
答案:
用户登录可进行刷题及查看答案
登录后提交答案