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中时，最短路径已完毕。
具体实现如下：
/*
Filename:dijkstra.cpp
Author: xiaobing
E-mail: [email protected]
Date: 2013-08-30
*/
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<string.h>
#include<stack>
#define N 50
#define M 50
#define INF 0xfffffff
using namespace std;
/*
*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中时，最短路径已完毕。 */ /*
*dijkstra算法
*@node 总共的节点数
*@from 源点
*@map 点与点之间的权表
*@dis 源点到该点的最短距离
*@prev 存储当前的前一个经过的点
*/
void dijkstra(int node, int from, int map[][N], int dis[], int prev []){
int i,j,k;
//初始化为所有节点均为求出最短路径
int used[N] = {0};
//第一个点已使用，并且已求出
used[from] = 1;
//初始化源点到其他点的距离
for(i = 1;i <= node;i++){
dis[i] = map[from][i];
//如果源点到该点不可达，那么其前经过的点为0
//相反为from
if(dis[i] == INF || dis[i] == 0){
prev[i] = 0;
} else {
prev[i] = from;
}
}
int min;
//遍历node次，寻找每个点到源点的最短距离
for(i = 1;i <= node;i++){
//初始化为无穷大
min = INF;
//遍历其他没有加入used中的点，并找出最短路径的点k
for(j = 1;j <= node;j++){
if(!used[j] && dis[j] < min){
min = dis[j];
k = j;
}
} //将该点加入used中，表示已求出从源点到该点的最短路径
used[k] = 1; //更新与k相邻的点到源点的距离
//如果经过k点到j的距离更短，那么更新dis[j](从源点到j的距离)
//为源点到k的距离 + k到j的距离,即:dis[k] + map[k][j]
//并更新j的前一个经过的点为k
for(j = 1;j <= node;j++){
if(dis[j] > dis[k] + map[k][j]){
dis[j] = dis[k] + map[k][j];
prev[j] = k;
}
}
}
} //打印二维表
void print(int table[][M], int row, int col){
int i,j;
for(i = 0;i < row;i++){
for(j = 0;j < col;j++){
cout<<table[i][j]<<" ";
} cout<<endl;
}
} //打印路径,由于是一个点储存才是前置节点，可以用栈来存储
//from 为源点
//to 为目的点
//prev 为前置节点路径
void printPath(int from, int to, int prev[]){
stack<int> path;
//把目标点入栈
path.push(to);
//一直找到源点，当然，也可能没有源点，但那个点的前置节点为0
//这里需要防止环路，所以可以用距离来判断，当相等时，就退出了
while(prev[to] != 0){
path.push(prev[to]);
to = prev[to]; }
//如果栈顶节点不是源点，说明从源点到目标点不可达
if(path.top() != from){
cout<<"没有路径"<<endl;
return ;
} cout<<"路径为: "; int flag = 0; //第一次不输出指标
while(!path.empty()){
if(flag)
cout<<"->";
flag = 1;
cout<<path.top();
path.pop();
}
cout<<endl;
}
int main(){
int i, j;
//定义一个权表
int map[N][M];
//初始化map为INF
for(i = 0;i < N;i++){
for(j = 0;j < M;j++){
map[i][j] = INF;
if(i == j){
map[i][j] = 0;
}
}
}
//print(map, N, M);
//node 节点数
//line 边数
//start 源点
int node,line,start;
cin>>node;
cin>>line;
cin>>start; int from, to,len;
//接受数据并初始化map
for(i = 0;i < line;i++){
cin>>from>>to>>len;
map[from][to] = len;
}
cout<<endl;
cout<<"原始数据为:"<<endl;
print(map, node + 1, node + 1);
cout<<endl; //初始时所有的最短路径为0,前置节点为0
int dis[N] = {0};
int prev[N] = {0};
dijkstra(node, start, map, dis, prev);
for(i = 0;i <= node;i++){
cout<<prev[i]<<" ";
}
cout<<endl; cout<<"从节点"<<start<<"到其他节点的最短距离为:"<<endl; for(i = 1;i <= node;i++){
cout<<start<<"--"<<i<<"距离为："<<dis[i]<<endl;
printPath(start, i, prev);
}
return 0;
}
测试数据为：
5
7
1
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 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
路径为: 1
1--2距离为：10
路径为: 1->2
1--3距离为：50
路径为: 1->4->3
1--4距离为：30
路径为: 1->4
1--5距离为：60
路径为: 1->4->3->5 ===================================== 5
7
5
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 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
路径为: 2
2--3距离为：10
路径为: 2->3
2--4距离为：30
路径为: 2->4
2--5距离为：40
路径为: 2->4->5