用Dijkstra算法求图4-3中从点v1,到点vn(n=1,…,8)的最短路线,图4-3中直线上的数据表示相应两点间的距离。
正确答案:
根据最短路径法计算,如表4-8所示。
由表4-8可知,从点v1,到点vn(n=1,…,8)的最短路线具体如下:
(1)v1v2的最短路线为v1→v3→v2,距离为6;
(2)v1v3的最短路线为v1→v3,距离为2;
(3)v1v4的最短路线为v1→v3→v4,距离为4;
(4)v1v1的最短路线为v1→v3→v4→v6→v5,距离为7;
(5)v1v6的最短路线为v1→v3→v4→v6,距离为5;
(6)v1v7的最短路线为v1→v3→v4→v6→v7,距离为9;
(7)v1v8的最短路线为v1→v3→v4→v6→v5→v8,距离为8。
如图4-4所示,粗线部分为V1V8之间的最短路径。
由表4-8可知,从点v1,到点vn(n=1,…,8)的最短路线具体如下:
(1)v1v2的最短路线为v1→v3→v2,距离为6;
(2)v1v3的最短路线为v1→v3,距离为2;
(3)v1v4的最短路线为v1→v3→v4,距离为4;
(4)v1v1的最短路线为v1→v3→v4→v6→v5,距离为7;
(5)v1v6的最短路线为v1→v3→v4→v6,距离为5;
(6)v1v7的最短路线为v1→v3→v4→v6→v7,距离为9;
(7)v1v8的最短路线为v1→v3→v4→v6→v5→v8,距离为8。
如图4-4所示,粗线部分为V1V8之间的最短路径。
答案解析:有
微信扫一扫手机做题