【概述】

Dijkstra 算法是單源最短路徑算法，即計算起點只有一個的情況到其他點的最短路徑，其無法處理存在負邊權的情況。

其時間復雜度是：O(E+VlogV)

【算法分析】

將點分為兩類，一類是已確定最短路徑的點，稱為：白點，一類是未確定最短路徑的點，稱為：藍點。

求一個點的最短路徑，就是把這個點由藍點變為白點，從起點到藍點的最短路徑上的中轉點在這個時刻只能是白點。

Dijkstra 算法的思想，就是一開始將起點到終點的距離標記為 0，而后進行 n 次循環，每次找出一個到起點距離 dis[u] 最短的點 u ，將它從藍點變為白點，隨后枚舉所有白點 Vi，如果以此白點為中轉到達藍點 Vi 的路徑 dis[u]+w[u][vi] 更短的話，這將它作為 Vi 的更短路徑（此時還不能確定是不是Vi的最短路徑）。

以此類推，每找到一個白點，就嘗試用它修改其他所有藍點，中轉點先于終點變成白點，故每一個終點一定能被它的最后一個中轉點所修改，從而求得最短路徑。

以下圖為例

算法開始時，作為起點的 dis[1]=0，其他的點 dis[i]=0x3f3f3f3f

第一輪循環找到 dis[1] 最小，將 1 變為白點，對所有藍點進行修改，使得：dis[2]=2，dis[3]=4，dis[4]=7

此時，dis[2]、dis[3]、dis[4] 被它的最后一個中轉點 1 修改了最短路徑。

第二輪循環找到 dis[2] 最小，將 2 變成白點，對所有藍點進行修改，使得：dis[3]=3、dis[5]=4

此時，dis[3]、dis[5] 被它的最后一個中轉點 2 修改了最短路徑。

第三輪循環找到 dis[3] 最小，將 3 變成白點，對所有藍點進行修改，使得：dis[4]=4。

此時，dis[4] 被它的最后一個中轉點 3 修改了最短路徑，但發現以 3 為中轉不能修改 5，說明 3 不是 5 的最后一個中轉點。

接下來兩輪循環將 4、5 也變成白點。

N輪循環結束，所有點的最短路徑均可求出。

【算法描述】

設起點為 s，dis[v] 表示從 s 到 v 的最短路徑，pre[v] 為 v 的前驅結點，vis[v] 用于記錄 v 是否被訪問過。

1.初始化：

dis[v]=0x3f3f3f3f（v≠s），vis[v]=false，即：從始點到各點的值初始化為一極大值，所有點均標記為未訪問

dis[s]=0，pre[s]=0，即：始點到始點的距離為 0，且其沒有前驅結點

2.算法主體：

for(int i=1;i<=n;i++) {int min=INF;int u=0;for(int v=1;v<=n;v++) { //在沒有被訪問過的點中找一個頂點u，使得dis[u]是最小的if( vis[v]==false && dis[v]<min) {min=dis[v];u=v;}}if(u==0)break;vis[u]=true;//u標記為已確定的最短路徑for(int v=1;j<=n;j++) { //枚舉與u相連的每個未確定的最短路的頂點if(dis[u]+w[u][v]<dis[v]) {dis[j]=dis[u]+w[u][v]; //更新最短路徑pre[v]=u;//記錄前驅}} }

3.算法結束：

dis[v] 即為 s 到 v 最短距離，pre[v] 即為 v 的前驅結點，用來輸出路徑。

【模版】

1.簡化版

簡化版不可處理重邊圖

int dis[N];//單源最短距離 int G[N][N];//G[i][j]表示i到j的有向邊長 bool vis[N];//表示w[i]是否已經計算完 void dijkstra(int n,int s){for(int i=1;i<=n;i++){int x;//x標記當前最短w的點int min_dis=INF;//記錄當前最小距離for(int y=1;y<=n;y++){if(!vis[y] && min_dis>=dis[y]){x=y;min_dis=dis[x];}}vis[x]=true;for(int y=1;y<=n;y++) dis[y]=min(dis[y],dis[x]+G[x][y]);} } int main(){memset(dis,INF,sizeof(dis));memset(vis,0,sizeof(vis));int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,dis;scanf("%d%d%d",&x,&y,&dis);G[x][y] = G[y][x] = dis; //無向圖添邊一次,有向圖添邊兩次}int start;scanf("%d",&start);dijkstra(n,start);for(int i=1;i<=n;i++)printf("%d\n",dis[i]);return 0; }

2.標準版

標準版適用于稀疏圖，可處理重邊圖

int n,m; struct Edge{//邊int from;//邊的起點int to;//邊的終點int dis;//邊的長度Edge(int f,int t,int d){//構造函數from=f;to=t;dis=d;} };struct HeapNode{//Dijkstra用到的優先隊列的結點int dis;//點到起點距離int u;//點的序號HeapNode(int a,int b){dis=a;u=b;}bool operator < (const HeapNode &rhs) const {return dis > rhs.dis;} };struct Dijkstra{int n,m;//點數、邊數vector<Edge> edges;//邊列表vector<int> G[N];//每個結點出發的邊的編號bool vis[N];//是否走過int dis[N];//起點s到各點的距離int p[N];//從起點s到i的最短路中的最后一條邊的編號void init(int n) {//初始化this->n = n;for(int i=0;i<n;i++) //清空鄰接表G[i].clear();edges.clear();//清空邊列表}void AddEdge(int from,int to,int diss) {//添加邊，若為無向圖，調用兩次edges.push_back(Edge(from,to,diss));m=edges.size();//邊的個數G[from].push_back(m-1);//添加至邊列表}int dijkstra(int s) {//求s到所有點的距離memset(dis,INF,sizeof(dis));memset(vis,false,sizeof(vis));dis[s]=0;priority_queue<HeapNode> Q;//優先隊列Q.push(HeapNode(0,s));while(!Q.empty()) {HeapNode x=Q.top();Q.pop();int u=x.u;if(vis[u])//若已被訪問continue;vis[u]=true;//標記為已訪問for(int i=0;i<G[u].size();i++) {//枚舉所有與當前點相連的邊Edge &e=edges[G[u][i]];if(dis[e.to] > dis[u]+e.dis) {//更新距離dis[e.to] = dis[u]+e.dis;p[e.to]=G[u][i];Q.push(HeapNode(dis[e.to],e.to));}}}return dis[n];//返回起點s到終點n最短距離} }DJ;int main() {while(scanf("%d%d",&n,&m)!=EOF&&(n+m)){DJ.init(n);//初始化for(int i=0;i<m;i++) {int x,y,dis;scanf("%d%d%d",&x,&y,&dis);//無向圖添邊兩次DJ.AddEdge(x,y,dis);DJ.AddEdge(y,x,dis);}int start;scanf("%d",&start);DJ.dijkstra(start);//求start到各點的距離for(int i=0,j=0,s=++start;i<n;i++)//輸出start到各點的距離printf("%d->%d: %d\n",s,++j,DJ.dis[i]);}return 0; }

?

總結

以上是生活随笔為你收集整理的图论 —— 最短路 —— Dijkstra 算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。