更新所有的边,每条边更新V-1次,时间复杂度为O(V*E).
有些更新操作是重复了的,这里可以考虑检查多余的重复操作作,如果没有更新发生,则立即终止算法。
- #include<iostream>
- #include<malloc.h>
- #include<queue>
- #include <algorithm>
- #include<stdlib.h>
- #include<functional>
- using namespace std;
- #define maxNum 100 //定义邻接举证的最大定点数
- #define maxWeight 1000000 //边权最大值
- //顶点信息
- typedef struct
- {
- int id;
- int dist;
- }node;
- //图的邻接矩阵表示结构
- typedef struct
- {
- //char v[maxNum];//图的顶点信息
- node v[maxNum];
- int e[maxNum][maxNum];//图的顶点信息
- int vNum;//顶点个数
- int eNum;//边的个数
- }graph;
- //函数声明
- void createGraph(graph *g);//创建图g
- //Bellman_ford算法
- void Bellman_ford(graph *g)
- {
- int k,i,j;
- //初始化dist的值
- for(i=1;i<=g->vNum;i++)
- {
- g->v[i].dist=maxWeight; //dist为最大值
- g->v[i].id=i;
- }
- g->v[1].dist=0;//1作为源点,dist为0
- for(k=1;k<=g->vNum;k++)//V-1次循环
- {
- for(i=1;i<=g->vNum;i++)
- {
- for(j=1;j<=g->vNum;j++)
- {
- if(g->e[i][j]!=maxWeight)
- if(g->v[j].dist>(g->v[i].dist+g->e[i][j]))
- g->v[j].dist=g->v[i].dist+g->e[i][j];
- }
- }
- //for(int p=1;p<=g->vNum;p++)//输出每次更新完以后的dist
- // cout<<g->v[p].dist<<" ";
- //cout<<endl;
- }
- }
- void createGraph(graph *g)//创建图g
- {
- cout<<"正在创建无向图..."<<endl;
- cout<<"请输入顶点个数vNum:";
- cin>>g->vNum;
- int i,j;
- //构造邻接矩阵,顶点到自身的距离是无穷大的。
- cout<<"输入邻接矩阵权值:"<<endl;
- for(i=1;i<=g->vNum;i++)
- for(j=1;j<=g->vNum;j++)
- {
- cin>>g->e[i][j];
- if(g->e[i][j]==0)
- g->e[i][j]=maxWeight;
- }
- }
- int main()
- {
- graph *g;
- g=(graph*)malloc(sizeof(graph));
- createGraph(g);
- Bellman_ford(g);
- cout<<"Dijkstra算法单源(源为1)最短路径为:"<<endl;
- for(int k=1; k<=g->vNum; k++)
- {
- cout<<g->v[k].dist<<" ";
- }
- cout<<endl;
- system("pause");
- return 0;
- }
- /*
- 正在创建无向图...
- 请输入顶点个数vNum:8
- 输入邻接矩阵权值:
- 0 10 0 0 0 0 0 8
- 0 0 0 0 0 2 0 0
- 0 1 0 1 0 0 0 0
- 0 0 0 0 3 0 0 0
- 0 0 0 0 0 -1 0 0
- 0 0 -2 0 0 0 0 0
- 0 -4 0 0 0 -1 0 0
- 0 0 0 0 0 0 1 0
- Dijkstra算法单源(源为1)最短路径为:
- 0 5 5 6 9 7 9 8
- 请按任意键继续. . .
- */
ps:2011-6-15
1.修改:dist单独列出一个数组存放,不在将dist值存放在图中。
2.输出dist修改过程,发现后续的dist没有发生变化,可以通过一个检查函数来判断,如果dist前后没有发生变化则表明已经找到最短路径
代码实例:
- #include<iostream>
- #include<malloc.h>
- #include<queue>
- #include <algorithm>
- #include<stdlib.h>
- #include<functional>
- using namespace std;
- #define maxNum 100 //定义邻接举证的最大定点数
- #define maxWeight 1000000 //边权最大值
- int dist[maxNum];//定义数组,默认情况下数组中的所有元素都为0
- //图的邻接矩阵表示结构
- typedef struct
- {
- char v[maxNum];//图的顶点信息
- int e[maxNum][maxNum];//图的顶点信息
- int vNum;//顶点个数
- int eNum;//边的个数
- }graph;
- //函数声明
- void createGraph(graph *g);//创建图g
- void Bellman_ford(graph *g);
- //Bellman_ford算法
- void Bellman_ford(graph *g)
- {
- int k,i,j,p;
- //初始化dist的值
- for(i=1;i<=g->vNum;i++)
- {
- dist[i]=maxWeight;
- }
- dist[1]=0;
- for(i=1;i<=g->vNum;i++)
- {
- cout<<dist[i]<<" ";
- }
- cout<<endl;
- cout<<"输出"<<g->vNum<<"次迭代过程中的dist值"<<endl;
- for(k=1;k<=g->vNum;k++)//V-1次循环
- {
- //更新每一条边的权值
- for(i=1;i<=g->vNum;i++)
- {
- for(j=1;j<=g->vNum;j++)
- {
- if(g->e[i][j]!=maxWeight&&dist[i]!=maxWeight)//如果i->j之间存在路径
- {
- if(dist[j]>dist[i]+g->e[i][j])
- {
- dist[j]=dist[i]+g->e[i][j];
- }
- }
- }
- }
- for(i=1;i<=g->vNum;i++)
- {
- cout<<dist[i]<<" ";
- }
- cout<<endl;
- }
- }
- void createGraph(graph *g)//创建图g
- {
- cout<<"正在创建无向图..."<<endl;
- cout<<"请输入顶点个数vNum:";
- cin>>g->vNum;
- int i,j;
- //构造邻接矩阵,顶点到自身的距离是无穷大的。
- cout<<"输入邻接矩阵权值:"<<endl;
- for(i=1;i<=g->vNum;i++)
- for(j=1;j<=g->vNum;j++)
- {
- cin>>g->e[i][j];
- if(g->e[i][j]==0)
- g->e[i][j]=maxWeight;
- }
- }
- int main()
- {
- graph *g;
- g=(graph*)malloc(sizeof(graph));
- createGraph(g);
- Bellman_ford(g);
- cout<<"Dijkstra算法单源(源为1)最短路径为:"<<endl;
- for(int k=1; k<=g->vNum; k++)
- {
- cout<<dist[k]<<" ";
- }
- cout<<endl;
- system("pause");
- return 0;
- }
- /*
- 正在创建无向图...
- 请输入顶点个数vNum:8
- 输入邻接矩阵权值:
- 0 10 0 0 0 0 0 8
- 0 0 0 0 0 2 0 0
- 0 1 0 1 0 0 0 0
- 0 0 0 0 3 0 0 0
- 0 0 0 0 0 -1 0 0
- 0 0 -2 0 0 0 0 0
- 0 -4 0 0 0 -1 0 0
- 0 0 0 0 0 0 1 0
- 0 1000000 1000000 1000000 1000000 1000000 1000000 1000000
- 输出8次迭代过程中的dist值
- 0 10 10 1000000 1000000 12 9 8
- 0 5 10 11 14 8 9 8
- 0 5 5 11 14 7 9 8
- 0 5 5 6 9 7 9 8
- 0 5 5 6 9 7 9 8
- 0 5 5 6 9 7 9 8
- 0 5 5 6 9 7 9 8
- 0 5 5 6 9 7 9 8
- Dijkstra算法单源(源为1)最短路径为:
- 0 5 5 6 9 7 9 8
- 请按任意键继续. . .
- */
本文转自xwdreamer博客园博客,原文链接:http://www.cnblogs.com/xwdreamer/archive/2011/06/14/2297002.html,如需转载请自行联系原作者