單源最短路徑dijkstra算法的初步學習（1）

今天學長給我們講了求最短路的4種算法以及它們具體的應用。然後今晚寫了好久才把第一個dijkstra算法寫好。。。。。。。。

對于dijkstra算法共有3個版本：基礎版及用優先隊列,堆進行優化的版本。

對于基本版的算法，其實我覺得它和求最小生成樹的prime()算法很是類似,無論是從思想還是代碼的實作上。

我把它的代碼分為2個部分,第一部分是初始化:包括dist數組，visited數組。第二部分是在n次循環的過程中

利用貪心的實作每次找到一個dist值最小的頂點,然後标記,然後再對和這個頂點相連的其它頂點的dist值進行

修改。這個思路的時間複雜度為n^2。

具體代碼如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define Max 100
#define INF 1<<30   //不要用0x7fffffff表示最大值 

//fa[]數組存儲每個頂點的父節點好用于列印路徑 
int fa[Max],visited[Max],dist[Max]; //dist數組用來儲存每個點到源點的最短路徑長度 
int map[Max][Max];
int n,m;  //n個頂點m條邊的有向圖 

void dijkstra(int s)  //s開始的單源最短路 
{
     int i,j,k;
     for(i=0;i<n;i++)  //初始化fa[]數組(此處不是必要的) 
         fa[i]=i; 
     memset(visited,0,sizeof(visited));  //初始化通路标記數組
     for(i=0;i<n;i++)
     { 
        dist[i]=map[s][i];    //初始化dist[]數組
        if(map[s][i]<INF)   //将與s相鄰的頂點的父節點改為s 
           fa[i]=s; 
     } 
     visited[s]=1;  //标記源點已通路
     for(i=0;i<n;i++)   //進行n次循環
     {
         int min=INF,mini;
         for(j=0;j<n;j++)  //尋找與源點距離最短的點 
         {
             if(!visited[j]&&dist[j]<min)
             {
                  min=dist[j];
                  mini=j;                   
             }
         } 
         visited[mini]=1;  //标記
         for(j=0;j<n;j++)   //對mini的相鄰點的dist值進行更新 
            if(!visited[j]&&dist[mini]+map[mini][j]<dist[j])
            {
                  dist[j]=dist[mini]+map[mini][j];
                  fa[j]=mini;   //更新父節點資訊 
            }     
     } 
} 

bool used[Max];
void Init()  //圖鄰接矩陣的初始化 
{
    int i,j;
    for(i=0;i<n;i++)
    {
       for(j=0;j<n;j++)
           map[i][j]=INF;  //圖中所有邊的權值初始都為無窮大
        map[i][i]=0;    //保證源點到自身的最短路為0 
    } 
} 

int main()
{
    int i,j,k1,k2,w;
    while(cin>>n>>m)
    {
         Init(); 
         for(i=0;i<m;i++)
         {
             cin>>k1>>k2>>w;
             map[k1][k2]=w;
         }
         dijkstra(0);
         for(i=0;i<n;i++)
            cout<<dist[i]<<" ";
         cout<<endl;
    }
} 
           

第二種思路是用鄰接表和優先隊列對上面的代碼實行優化。具體的優化有兩個地方:第一個是利用優先隊列的性質

優化尋找具有最小dist值頂點i的過程；這個需要自定義一個小整數優先的優先隊列,定義好後，每次尋找隻需要一個p.top()就行。第二個是用鄰接表優化對i的鄰結點的通路；用鄰接矩陣表示圖的時候對每一個頂點都要試探一下是不是

i的鄰結點,而用鄰接表表示後就能保證隻通路i的鄰結點而不會有多餘的試探了。經過這兩個優化後，算法的時間複雜度就降為mlongn了(m是邊數)。是以這種算法适用于邊比較少的稀疏圖，不過劉汝佳講無論邊多不多，反正下面這個

都要比上面那個快。。。。。。。。

代碼如下：

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>//使用pair的頭檔案
using namespace std;

#define INF 1<<30
#define Max 1000

int n,m;
int fa[Max],visited[Max],dist[Max];
int first[Max],u[Max],v[Max];
int w[Max],next[Max];

typedef pair<int,int> pii;   //定義此類型配合優先隊列的使用
priority_queue<pii,vector<pii>,greater<pii> >q;  //定義了一個pill型,小整數優先的優先隊列

void dijkstra(int s)
{
     int i,j,k;
     for(i=0;i<n;i++)  //dist初始化
        dist[i]=i==s?0:INF;//與前面不同,此次隻将源點自己到自己的dist值初始化為0,而不管他的鄰結點   
     memset(visited,0,sizeof(visited));  //初始化通路标記數組
     q.push(make_pair(dist[s],s));  // 用源點初始化優先隊列
     while(!q.empty())
     {
         pii u=q.top();q.pop();//取出dist值最小的點
         int x=u.second;  //取出dist值最小點的頂點編号
         if(visited[x])    //如果已經通路過了抛棄這個點 
            continue; 
         visited[x]=1;
         for(int e=first[x];e!=-1;e=next[e])   //鄰接表主要用來優化尋找從x出發的邊這一步 
             if(dist[v[e]]>dist[x]+w[e])  // 第e條邊(即以x為起點,v[e]為終點的邊的權值可直接由w[e]得) 
             {
                 dist[v[e]]=dist[x]+w[e];  //更新dist 
                 fa[v[e]]=x;  //更新父節點資訊
                 q.push(make_pair(dist[v[e]],v[e]));  //将更新過的頂點入隊 
             } 
     } 
} 

int main()
{
    int i,j,k;
    while(cin>>n>>m)
    {
         for(i=0;i<n;i++)
             first[i]=-1;  //初始表頭first數組
         for(int e=0;e<m;e++)
         {
             cin>>u[e]>>v[e]>>w[e];//輸入第e條邊的起點 終點 權值
             next[e]=first[u[e]];  //頭插法 
             first[u[e]]=e; 
         } 
         dijkstra(0);
         for(i=0;i<n;i++)
             cout<<dist[i]<<" ";
         cout<<endl; 
    }
} 
           

對于第3種利用堆進行優化的代碼和上面第2種很像,主要好像是省了一個visited[]标記數組；但是雖然代碼我寫

出來了,但原理還是不太懂,明天還得請教一下

代碼如下：

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>//使用pair的頭檔案
using namespace std;

#define INF 1<<30
#define Max 1000

int n,m;
int fa[Max],visited[Max],dist[Max];
int first[Max],u[Max],v[Max];
int w[Max],next[Max];

typedef pair<int,int> pii;   
priority_queue<pii,vector<pii>,greater<pii> >q;  

void dijkstra(int s)
{
     int i,j,k;
     for(i=0;i<n;i++)  
        dist[i]=i==s?0:INF;
     q.push(make_pair(dist[s],s));  
     while(!q.empty())
     {
		 while(!q.empty()&&q.top().first>dist[q.top().second]) q.pop();  //這一句是堆優化的關鍵之處,應該是可以避免重複通路,但現在我還不是太了解原理
		 if(q.empty()) break;
         pii u=q.top();q.pop();//取出dist值最小的點
         int x=u.second;  //取出dist值最小點的頂點編号
         for(int e=first[x];e!=-1;e=next[e])   //鄰接表主要用來優化尋找從x出發的邊這一步 
             if(dist[v[e]]>dist[x]+w[e])  // 第e條邊(即以x為起點,v[e]為終點的邊的權值可直接由w[e]得) 
             {
                 dist[v[e]]=dist[x]+w[e];  //更新dist 
                 fa[v[e]]=x;  //更新父節點資訊
                 q.push(make_pair(dist[v[e]],v[e]));  //将更新過的頂點入隊 
             } 
     } 
} 

int main()
{
    int i,j,k;
    while(cin>>n>>m)
    {
         for(i=0;i<n;i++)
             first[i]=-1;  //初始表頭first數組
         for(int e=0;e<m;e++)
         {
             cin>>u[e]>>v[e]>>w[e];//輸入第e條邊的起點 終點 權值
             next[e]=first[u[e]];  //頭插法 
             first[u[e]]=e; 
         } 
         dijkstra(0);
         for(i=0;i<n;i++)
             cout<<dist[i]<<" ";
         cout<<endl; 
    }
}