通信人家园

标题: 无向网络最短路径求解算法之——Dijkstra算法 [查看完整版帖子] [打印本页]

时间: 2015-2-25 18:09

作者: aries100 标题: 无向网络最短路径求解算法之——Dijkstra算法

如何求图中V0到V5的最短路径呢？

      java实现的方式如下：
   第一步，根据图来建立权值矩阵：
   int[][] W = {
{  0, 1, 4,  -1,  -1,  -1 },
{  1, 0, 2, 7, 5,  -1 },
{  4, 2, 0,  -1, 1,  -1 },
{ -1,  7,  -1, 0, 3, 2 },
{ -1,  5, 1, 3, 0, 6 },
{ -1, -1,  -1, 2, 6, 0 } };(-1表示两边不相邻,权值无限大)
例如：W[0][2]=4 表示点V0到点V2的权值为4
W[0][3]=-1表示点V0与V3不相邻，所以权值无限大。
第二步：对V0标号；V0到其它点的路径得到 distance: {0,1,4,-1,-1,-1}; 找到V0到各点中权值最小的那个点（标号的点除外,-1代表无限大），故得到1即对应的下标1，得到V1；对V1标号，然后更改V0通过V1到其它点的路径得到 distance: { 0, 1, 3, 8, 6, -1};
第三步：找到distance中权值最小的那个点，（标号的点除外）得到V2,对V2标号，然后更改V0通过V1->V2到其它点的路径得到 distance: { 0, 1, 3, 8, 4, -1};
第四步：找到distance中权值最小的那个点，（标号的点除外）得到V4,对V4标号，然后更改V0通过V1->V2到其它点的路径得到 distance: { 0, 1, 3, 7, 4, 10};
第四步：找到distance中权值最小的那个点，（标号的点除外）得到V3,对V3标号，然后更改V0通过V1->V2到其它点的路径得到 distance: { 0, 1, 3, 7, 4, 9};
最后只剩下V5没有被标号，就找到V5了。结束！

时间: 2015-3-2 11:31

作者: baidu2009

学习，学习！

时间: 2015-3-2 13:41

作者: OpSword

谢谢分享

时间: 2015-9-21 16:06

作者: aries100

亲们，太客气了。

通信人家园 (https://www.txrjy.com/)