一个5000乘上5000的稀疏矩阵，如何利用MATLAB求解平均最短路径，算法要求用dijkstra
发布网友
发布时间：2022-04-24 01:58
共1个回答
热心网友
时间：2023-10-20 10:56
两个指定顶点之间的最短路径
问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。
以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对
G的每一边e，赋以一个实数)(ew—直通铁路的长度，称为e的权，得到赋权图G。G的
子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点00,vu间的具最小权的轨。这条轨叫做00,vu间的最短路，它的权叫做00,vu间的距离，亦记作),(00vud。
求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距0u从近到远为顺序，依次求得0u到G的各顶点的最短路和距离，直至0v（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。
(i) 令0)(0ul，对0uv，令)(vl，}{00uS，0i。 (ii) 对每个iSv（iiSVS\），用
)}()(),({minuvwulvli
Su
代替)(vl。计算)}({minvli
Sv，把达到这个最小值的一个顶点记为1iu，令}{11iiiuSS。
(iii). 若1||Vi，停止；若1||Vi，用1i代替i，转(ii)。
算法结束时，从0u到各顶点v的距离由v的最后一次的标号)(vl给出。在v进入iS之前的标号)(vl叫T标号，v进入iS时的标号)(vl叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，0u至各项点的最短路也在图上标示出来了。
例1 某公司在六个城市126,,,cccL中有分公司，从ic到jc的直接航程票价记在下述矩阵的),(ji位置上。（表示无直接航路），请帮助该公司设计一张城市1c到其它城市间的票价最便宜的路线图。
055252510
5追问提示就只是说了利用稀疏矩阵的特点，虽然是这么大的矩阵，但是只有大约50000个1，在这个里面。我就是不知道，怎么利用稀疏矩阵加速。
我编了一个程序，在小的矩阵上试了一下，是对的。但是，现在就是对这5000个节点只运行一次，就感觉需要很长时间，运行了5分钟都没有停下来。更不用提要对5000个都跑一次
热心网友
时间：2023-10-20 10:56
两个指定顶点之间的最短路径
问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。
以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对
G的每一边e，赋以一个实数)(ew—直通铁路的长度，称为e的权，得到赋权图G。G的
子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点00,vu间的具最小权的轨。这条轨叫做00,vu间的最短路，它的权叫做00,vu间的距离，亦记作),(00vud。
求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距0u从近到远为顺序，依次求得0u到G的各顶点的最短路和距离，直至0v（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。
(i) 令0)(0ul，对0uv，令)(vl，}{00uS，0i。 (ii) 对每个iSv（iiSVS\），用
)}()(),({minuvwulvli
Su
代替)(vl。计算)}({minvli
Sv，把达到这个最小值的一个顶点记为1iu，令}{11iiiuSS。
(iii). 若1||Vi，停止；若1||Vi，用1i代替i，转(ii)。
算法结束时，从0u到各顶点v的距离由v的最后一次的标号)(vl给出。在v进入iS之前的标号)(vl叫T标号，v进入iS时的标号)(vl叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，0u至各项点的最短路也在图上标示出来了。
例1 某公司在六个城市126,,,cccL中有分公司，从ic到jc的直接航程票价记在下述矩阵的),(ji位置上。（表示无直接航路），请帮助该公司设计一张城市1c到其它城市间的票价最便宜的路线图。
055252510
5追问提示就只是说了利用稀疏矩阵的特点，虽然是这么大的矩阵，但是只有大约50000个1，在这个里面。我就是不知道，怎么利用稀疏矩阵加速。
我编了一个程序，在小的矩阵上试了一下，是对的。但是，现在就是对这5000个节点只运行一次，就感觉需要很长时间，运行了5分钟都没有停下来。更不用提要对5000个都跑一次
