本文实现的Dijkstra算法是最简单的方法，就是暴力搜索，其时间复杂度为O(V^2)，后面会使用优先队列的方法，修改广度优先遍历来实现Dijkstra算法，这样的算法时间复杂度上会有所改善。
代码实例：
- /*
- 参考文献：http://baike.baidu.com/view/7839.htm
- 算法流程:
- 在以下说明中，s为源，w[u,v]为点u和v之间的边的长度，结果保存在dist[]
- 1.初始化：源的距离dist[s]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。
- 2.循环n-1次：
- 在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
- 对于每个与u相邻的点v，执行Relax(u,v)，也就是说，如果dist[u]+w[u,v]<dist[v]，
- 那么把dist[v]更新成更短的距离dist[u]+w[u,v]。此时到点v的最短路径上，前一个节点即为u。
- 3.结束。此时对于任意的u，dist[u]就是s到u的距离。
- 直接实现:（本实例所采用的方法）
- 最简单的实现方法就是，在每次循环中，再用一个循环找距离最短的点，然后用任意的方法更新与其相邻的边，时间复杂度显然为O(n2)
- */
- #include<fstream>
- #include<cstring>
- #include<iostream>
- #include<stdlib.h>
- using namespace std;
- const int MaxNum=1000000; //边权最大值
- int n; //节点数目
- int dist[501]; //到节点1的最短路径值
- bool state[501]; //节点被搜索过状态指示
- int data[501][501]; //邻接矩阵
- //查找权值最小的节点
- int findmin()
- {
- int minnode=0, min=MaxNum,i;
- for(i=1;i<=n;i++)
- if((dist[i]<min)&&(!state[i]))
- {
- min=dist[i];
- minnode=i;
- }
- return minnode;//如果minnode=0则表示没有找到最小节点
- }
- void Dijkstra()
- {
- cout<<"输入定点数："<<endl;
- cin>>n;//输入顶点数量
- //构造邻接矩阵，顶点到自身的距离是无穷大的。
- cout<<"输入邻接矩阵权值："<<endl;
- for(int p=1; p<=n; p++)
- for(int q=1; q<=n; q++)
- {
- //in >> data[p][q];
- cin>>data[p][q];
- if (data[p][q]==0)
- data[p][q]=MaxNum;
- }
- //初始化
- for(int i=1; i<=n; i++)
- {
- state[i]=0;//初始化，表示所有点都没有被扩展过
- dist[i]=data[1][i];//data[1][i]表示1为源点
- }
- state[1]=true;
- int done=1;
- while (done<n)//循环n-1次
- {
- int node=findmin();
- if (node!=0)
- {
- done++; //找到的点的数目加1
- state[node]=true; //标记已经找到了从节点1到节点node的最短路径
- for(int i=1; i<=n; i++)//更新还没有找到的点的路径值
- if ((dist[i]>dist[node]+data[node][i]) && (!state[i]))
- dist[i]=dist[node]+data[node][i];
- }
- else
- break;
- }
- }
- int main()
- {
- Dijkstra();
- for(int k=1; k<=n; k++)
- {
- if (dist[k]==MaxNum)
- cout<<-1;
- else
- cout<<dist[k];
- if(k==n)
- cout<<endl;//最后输出换行
- else
- cout<<" ";//没到最后则以空字符间隔
- }
- system("pause");
- return 0;
- }
- /*
- 输入定点数：
- 5
- 输入邻接矩阵权值：
- 0 4 2 0 0
- 0 0 3 2 3
- 0 1 0 4 5
- 0 0 0 0 0
- 0 0 0 1 0
- */
PS:2011-6-15
修改部分：
输出了过程中dist[i]的变化
- #include<fstream>
- #include<cstring>
- #include<iostream>
- #include<stdlib.h>
- using namespace std;
- const int MaxNum=1000000; //边权最大值
- int n; //节点数目
- int dist[501]; //到节点1的最短路径值
- bool state[501]; //节点被搜索过状态指示
- int data[501][501]; //邻接矩阵
- //查找权值最小的节点
- int findmin()
- {
- int minnode=0, min=MaxNum,i;
- for(i=1;i<=n;i++)
- if((dist[i]<min)&&(!state[i]))
- {
- min=dist[i];
- minnode=i;
- }
- return minnode;//如果minnode=0则表示没有找到最小节点
- }
- void Dijkstra()
- {
- cout<<"输入定点数："<<endl;
- cin>>n;//输入顶点数量
- //构造邻接矩阵，顶点到自身的距离是无穷大的。
- cout<<"输入邻接矩阵权值："<<endl;
- for(int p=1; p<=n; p++)
- for(int q=1; q<=n; q++)
- {
- //in >> data[p][q];
- cin>>data[p][q];
- if (data[p][q]==0)
- data[p][q]=MaxNum;
- }
- //初始化
- for(int i=1; i<=n; i++)
- {
- state[i]=0;//初始化，表示所有点都没有被扩展过
- dist[i]=data[1][i];//data[1][i]表示1为源点
- }
- cout<<"输出过程中的dist[i]"<<endl;
- for(int i=1; i<=n; i++)
- {
- cout<<dist[i]<<" ";
- }
- cout<<endl;
- state[1]=true;
- int done=1;
- while (done<n)//循环n-1次
- {
- int node=findmin();
- if (node!=0)
- {
- done++; //找到的点的数目加1
- state[node]=true; //标记已经找到了从节点1到节点node的最短路径
- for(int i=1; i<=n; i++)//更新还没有找到的点的路径值
- if ((dist[i]>dist[node]+data[node][i]) && (!state[i]))
- dist[i]=dist[node]+data[node][i];
- for(int j=1;j<=n;j++)
- cout<<dist[j]<<" ";
- cout<<endl;
- }
- else
- break;
- }
- }
- int main()
- {
- Dijkstra();
- cout<<"输出最终dist[i]的值，-1表示源点"<<endl;
- for(int k=1; k<=n; k++)
- {
- if (dist[k]==MaxNum)
- cout<<-1;
- else
- cout<<dist[k];
- if(k==n)
- cout<<endl;//最后输出换行
- else
- cout<<" ";//没到最后则以空字符间隔
- }
- system("pause");
- return 0;
- }
- /*
- 输入定点数：
- 5
- 输入邻接矩阵权值：
- 0 4 2 0 0
- 0 0 3 2 3
- 0 1 0 4 5
- 0 0 0 0 0
- 0 0 0 1 0
- 输出过程中的dist[i]
- 1000000 4 2 1000000 1000000
- 1000000 3 2 6 7
- 1000000 3 2 5 6
- 1000000 3 2 5 6
- 1000000 3 2 5 6
- 输出最终dist[i]的值，-1表示源点
- -1 3 2 5 6
- 请按任意键继续. . .
- */
Dijkstra算法求单源最短路径，其实相当于是从一个源点S出发，找出从S出发可达的所有其他点的最短路径。
因此分以下几步完成：
1.dist[i]用于标记从s到i的最短路径，初始化是只有dist[s]=0,其他dist[i]=maxWeitht，表示权值无穷大
2.因为源点已经找到，还需要遍历剩余的V-1个点来找寻最短路径。
3.从dist[i]中找寻i点没有被访问且dist最小的值作为下一个顶点minnode。
4.如果dist[minnode]的值加上其可达顶点j的边上的值小于dist[j]的值，则更新dist[j]，表明j的前序节点是minnode。
本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2011/06/13/2297004.html，如需转载请自行联系原作者
