Dijkstra算法的实现及原理

算法用处与基本思想

Dijkstra算法的作用是求指定点到图中任何一点的最短路径。
其基本思路与BFS（深度优先搜索）有些类似，但不同的是BFS用的是一般队列，也就是严格的先进先出。而Dijkstra算法用到的则是优先队列。

什么是优先队列

优先队列中是有序的队列，其顺序取决于规定的规则。比如可以规定值大的在前面，也可以规定值小的在前面。一般来说直接用STL里面的priority_queue来实现，这个默认的是较大的值在前面。

算法过程

有一个保存到每个点最短路径的数组，这里记为shortlen[]（默认值为无穷，代表无通路）。还有一个记录点是否被访问过的数组，这里记为visit[]。
一开始，从起点开始，用每一个与起点相连的且没有被访问过的点的距离对shortlen数组进行更新，例如：第i个点与起始点的距离为x，x小于无穷，那么久把shortlen[i]的值更新为x。
只要有通路的点，全部放入优先队列然后把这个点记为被访问过。
然后就从队列里取出队头，将其当做新的起点，重新进行上面的操作。
当队列为空时跳出循环，这个时候的shortlen数组的值就是起点到各个点的最短距离。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=65535;
const int maxn=110;
unsigned int mp[maxn][maxn];
bool visit[maxn];
unsigned int shortlen[maxn];
typedef struct Node{
int dis,v;
bool operator < (const Node &cmp) const{//重载小于号，不理解的可以直接用。作用相当于定义一个优先队列的比较规则
return dis > cmp.dis;
    }
}Node;
void Dijkstra(int start,int num)
{
int value;
memset(visit,false,sizeof(visit));
memset(shortlen,INF,sizeof(shortlen));
    priority_queue<Node> q;
    shortlen[start]=0;
    q.push({0,start});//起点放入队列
while(!q.empty())
    {
        Node a=q.top();//取出
        q.pop();
        start=a.v;
        value=shortlen[start];
        visit[start]=true;//记为访问过
for(int i=1;i<=num;++i){
if(i==start)
continue;
if(mp[start][i]<INF&&visit[i]==false){
if(mp[start][i]+value<shortlen[i])
                        shortlen[i]=mp[start][i]+value;//更新数组
                    q.push({shortlen[i],i}); 
               }
        }
    }
}
int main()
{
// freopen("in.txt","r",stdin);
int numv;
int x,y,w,v;
cout<<"InPut the number of v"<<endl;
cin>>numv;
memset(mp,INF,sizeof(mp));
cout<<"Build Map"<<endl;
while(cin>>x>>y&&(x||y))
    {
cin>>w;
        mp[x][y]=w;
        mp[y][x]=w;
    }
cout<<"Input the start"<<endl;
cin>>v;

    Dijkstra(v,numv);
for(int i=1;i<=numv;++i)
cout<<"i="<<i<<" shortlen="<<shortlen[i]<<endl;
cout<<endl;
return 0;
}