Dijkstra算法求單源最短路徑（二）（BFS的改版）

該算法其實就是廣度優先算法的改版，隻是将廣度優先算法中的普通隊列改為了這裡的優先隊列。

#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，如需轉載請自行聯系原作者