Dijkstra算法模拟讲授

Dijkstra算法模拟讲解

 dijkstra算法，是一个求单源最短路径算法

其算法的特点为:       

         层层逼进，有点类似宽度搜索的感觉

         其需要的数据结构为:
                 int map[N][N] 所有点之间的权表
                 int dis[N] 所有点到源点的最短距离
                 int prev[N]   存储每个点的前一个经过的点，用于输出路径
                 int used[N]   用于存储已经求出最短路径的点
         则总的点减去used中的点，为还没有找出最短路径的点
         初始化时：map为实际存储的权，如果某一边没有，则设置为无穷大INF,自身设置0
         dis为源点到该点的距离，如果没有，也设置为无穷大INF
         prev，如果与源点相邻，则设置为源点，否则为0
         used 除了源点外，其余全为0
         第一次比较源点到其相邻的点，找出最短距离的点k，将其加入used[k] = 1;
         比较与k相邻的点j到源点的距离，如果比(dis[k] + map[k][j])源点到k + k
         到j点的距离大，那么更新dis[j] = dis[k] + map[k][j]，并记录prev[j] = k,
         表示j的前一个经过的点为k，再重复寻找其余的点到源点的最短距离，再把找到
         的点加入used中，直到全部节点都加入used中时，最短路径已完毕。

具体实现如下：

测试数据为：5711 2 101 4 301 5 1002 3 503 5 104 3 204 5 60原始数据为:0 268435455 268435455 268435455 268435455 268435455 268435455 0 10 268435455 30 100 268435455 268435455 0 50 268435455 268435455 268435455 268435455 268435455 0 268435455 10 268435455 268435455 268435455 20 0 60 268435455 268435455 268435455 268435455 268435455 0 0 0 1 4 1 3 从节点1到其他节点的最短距离为:1--1距离为：0路径为: 11--2距离为：10路径为: 1->21--3距离为：50路径为: 1->4->31--4距离为：30路径为: 1->41--5距离为：60路径为: 1->4->3->5=====================================5751 2 101 4 301 5 1002 3 503 5 104 3 204 5 60原始数据为:0 268435455 268435455 268435455 268435455 268435455 268435455 0 10 268435455 30 100 268435455 268435455 0 50 268435455 268435455 268435455 268435455 268435455 0 268435455 10 268435455 268435455 268435455 20 0 60 268435455 268435455 268435455 268435455 268435455 0 0 0 0 0 0 0 从节点5到其他节点的最短距离为:5--1距离为：268435455没有路径5--2距离为：268435455没有路径5--3距离为：268435455没有路径5--4距离为：268435455没有路径5--5距离为：0路径为: 5=====================================原始数据为:0 268435455 268435455 268435455 268435455 268435455 268435455 0 40 10 268435455 268435455 268435455 268435455 0 10 30 50 268435455 268435455 80 0 20 40 268435455 268435455 268435455 268435455 0 10 268435455 268435455 268435455 268435455 268435455 0 0 0 0 2 2 4 从节点2到其他节点的最短距离为:2--1距离为：268435455没有路径2--2距离为：0路径为: 22--3距离为：10路径为: 2->32--4距离为：30路径为: 2->42--5距离为：40路径为: 2->4->5

查看更多 下一篇