Dijkstra算法

我们用一个例子来具体说明Dijkstra算法的流程。

定义源点为0，dist[i]为源点0到顶点i的最短路径。其过程描述如下：

步骤 dist[1] dist[2] dist[3] dist[4] 已找到的集合
第1步 8 1 2 +∞ { 2 }
第2步 8 × 2 4 { 2, 3 }
第3步 5 × × 4 { 2, 3, 4 }
第4步 5 × × × { 2, 3, 4, 1 }
第5步 × × × × { 2, 3, 4, 1 }
第1步：从源点0开始，找到与其邻接的点：1，2，3，更新dist[]数组，因0不与4邻接，故dist[4]为正无穷。在dist[]中找到最小值，其顶点为2，即此时已找到0到2的最短路。

第2步：从2开始，继续更新dist[]数组：2与1不邻接，不更新；2与3邻接，因0→2→3比dist[3]大，故不更新dist[3] ；2与4邻接，因0→2→4比dist[4]小，故更新dist[4]为4。在dist[]中找到最小值，其顶点为3，即此时又找到0到3的最短路。

第3步：从3开始，继续更新dist[]数组：3与1邻接，因0→3→1比dist[1]小，更新dist[1]为5；3与4邻接，因0→3→4比dist[4]大，故不更新。在dist[]中找到最小值，其顶点为4，即此时又找到0到4的最短路。

第4步：从4开始，继续更新dist[]数组：4与1不邻接，不更新。在dist[]中找到最小值，其顶点为1，即此时又找到0到1的最短路。

第5步：所有点都已找到，停止。

对于上述步骤，你可能存在以下的疑问：

若A作为源点，与其邻接的只有B，C，D三点，其dist[]最小时顶点为C，即就可以确定A→C为A到C的最短路。但是我们存在疑问的是：是否还存在另一条路径使A到C的距离更小？ 用反证法证明。

假设存在如上图的红色虚线路径，使A→D→C的距离更小，那么A→D作为A→D→C的子路径，其距离也比A→C小，这与前面所述“dist[]最小时顶点为C”矛盾，故假设不成立。因此这个疑问不存在。

根据上面的证明，我们可以推断出，Dijkstra每次循环都可以确定一个顶点的最短路径，故程序需要循环n-1次。

#include<iostream>
#include<sstream>
using namespace std;
const int Max=100;
string Int_to_String(int n)//int转换string 
{
ostringstream stream;
stream<<n; //n为int类型
return stream.str();
}
class MGraph{
    public:
        MGraph(){

        }
        MGraph(int n,int e);
        ~MGraph(){

        }
    public:
    int vertex[Max];
    int arc[Max][Max];
    int vertexNum,arcNum;
};
MGraph::MGraph(int n,int e){
    int i,j;
    vertexNum=n;
    arcNum=e;
    for(int i=0;i<vertexNum;i++)
    vertex[i]=i;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    arc[i][j]=10000;
    cout<<"请输入图中各边的情况："<<endl;
    for(int k=0;k<e;k++){
        cin>>i>>j;
        cin>>arc[i][j];
    }
}
void Dijkstra(MGraph G,int v){
    int dist[Max],s[Max];
    string path[Max]; 
    for(int i=0;i<G.vertexNum;i++)
    {
    dist[i]=G.arc[v][i];
    if(dist[i]!=10000)
    path[i]=Int_to_String(G.vertex[v])+"->"+Int_to_String(G.vertex[i]);
    else
    path[i]="";
    }
    s[0]=v;
    dist[v]=0;
    int num=1;
    for(int i=0;i<G.vertexNum;i++)
    {
    int t=10000,k;
    for(int j=0;j<G.vertexNum;j++)
    {
        if(dist[j]<t&&dist[j]!=0)
        {
        t=dist[j];
        k=j;
        }
    }
    cout<<"终点为："<<k<<"  最短路径长度为："<<dist[k]<<"  过程："<<path[k]<<endl;
    s[num++]=k;
    for(int j=0;j<G.vertexNum;j++){
        if(dist[j]!=0&&dist[j]>(dist[k]+G.arc[k][j])){
            dist[j]=dist[k]+G.arc[k][j];
            path[j]=path[k]+"->"+Int_to_String(j);
        }
    }
    dist[k]=0;
    if(num==G.vertexNum)
    break;
    }
    cout<<"找到终点的顺序为："<<endl;
    for(int i=1;i<num;i++)
    cout<<s[i]<<" "; 
    cout<<endl;
}
int main(){
   int n,e,v;
   cout<<"输入起点下标："<<endl; 
   cin>>v;
   cout<<"输入图的顶点数和边数："<<endl;
   cin>>n>>e;
   MGraph G(n,e);
   Dijkstra(G,v);
   return 0;
}

代码如有错误，欢迎大家指点出来！