1.解析
该算法其实就是广度优先算法的改版，只是将广度优先算法中的普通队列改为了这里的优先队列。
2.算法实例
- #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
- int cmp(node a,node b);//定义优先队列以升序还是降序排列
- void Dijkstra(graph *g);//核心算法，是BFS的改版，只是将普通队列改成了优先队列。
- //定义排序类型。以node中dist升序排列
- int cmp(node a,node b)
- {
- return a.dist<b.dist;// 升序
- }
- //Dijkstra算法
- void Dijkstra(graph *g)
- {
- node Q[maxNum]; //定义结构体数组
- int front;//队列头
- int rear;//队列尾
- int count;//队列计数
- front=rear=count=0;//表示队列为空
- 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
- //以下两行是元素进队列操作
- Q[++rear]=g->v[1];
- count++;//顶点进入队列Q
- while(count>0)
- {
- sort(Q+front+1,Q+rear+1,cmp);//对队列Q进行排序，按dist的降序排列。
- //以下两行是队列的出队操作
- node n1=Q[++front];
- count--;//出队列操作
- k=n1.id;//优先队列中会取出队列中最小值就是最短路径
- for(j=1;j<=g->vNum;j++)
- {
- if(g->e[k][j]!=maxWeight)//k->j之间有边
- {
- if(g->v[j].dist>(g->v[k].dist+g->e[k][j]))
- {
- g->v[j].dist=g->v[k].dist+g->e[k][j];
- Q[++rear]=g->v[j];
- count++;
- }
- }
- }
- }
- }
- 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);
- Dijkstra(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: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
- Dijkstra算法单源(源为1)最短路径为：
- 0 3 2 5 6
- 请按任意键继续. . .
- */
本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2011/06/14/2297003.html，如需转载请自行联系原作者
