利用Dijkstra算法求下图中从顶点1到其它各顶点间的最短路径,按下面表格形式
3个回答
展开全部
v1到v2:10为最短路径;
v1到v3:7为最短路径;
v1到v4:8为最短路径;
v1到v5:v1-> v2 -> v5 =10+6= 16;v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15为最短路径;
v1到v6:v1v2v3v6=10+2+9=21;v1v3v6=7+9=16;v1v4v6=8+5=13;13为最短路径;
v1到v7:v1v2v5v7=10+6+20=36;v1v3v5v7=7+9+20=36;v1v3v6v7=7+9+30=46;
v1v4v6v7=8+5+30=42;v1v4v6v5v7=35;35为最短路径
Dijkstra:
求单源、无负权的最短路。时效性较好,时间复杂度为O(V*V+E)。源点可达的话,O(V*lgV+E*lgV)=>O(E*lgV)。当是稀疏图的情况时,此时E=V*V/lgV,所以算法的时间复杂度可为O(V^2)。若是斐波那契堆作优先队列的话,算法时间复杂度,则为O(V*lgV + E)。
以上内容参考:百度百科-最短路径算法
展开全部
v1到v2:10为最短路径;
v1到v3:7为最短路径;
v1到v4:8为最短路径;
v1到v5:v1-> v2 -> v5 =10+6= 16;v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15为最短路径;
v1到v6:v1v2v3v6=10+2+9=21;v1v3v6=7+9=16;v1v4v6=8+5=13;13为最短路径;
v1到v7:v1v2v5v7=10+6+20=36;v1v3v5v7=7+9+20=36;v1v3v6v7=7+9+30=46;
v1v4v6v7=8+5+30=42;v1v4v6v5v7=35;35为最短路径
v1到v3:7为最短路径;
v1到v4:8为最短路径;
v1到v5:v1-> v2 -> v5 =10+6= 16;v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15为最短路径;
v1到v6:v1v2v3v6=10+2+9=21;v1v3v6=7+9=16;v1v4v6=8+5=13;13为最短路径;
v1到v7:v1v2v5v7=10+6+20=36;v1v3v5v7=7+9+20=36;v1v3v6v7=7+9+30=46;
v1v4v6v7=8+5+30=42;v1v4v6v5v7=35;35为最短路径
本回答被网友采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询