資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學C++ Dijkstra 最短路徑演算法程式？
Dijkstra演算法（或Dijkstra最短路徑優先演算法，SPF演算法）是一種用於查詢圖中節點之間最短路徑的演算法，例如，它可以表示道路網路。該演算法從起始頂點（源點）建立一個到圖中所有其他點的最短路徑樹。
Dijkstra演算法透過構建一個集合，其中包含與源點距離最小的節點，來查詢從單個源節點到所有其他節點的最短路徑樹。
圖包含以下內容：
頂點或節點，在演算法中用v或u表示。
連線兩個節點的加權邊：(u,v)表示一條邊，w(u,v)表示其權重。在右圖中，每條邊的權重都以灰色顯示。
演算法步驟
- 將所有頂點的距離設定為無窮大，除了源頂點，將源頂點的距離設定為0。
- 以(距離，頂點)的形式將源頂點壓入最小優先順序佇列，因為最小優先順序佇列中的比較將根據頂點的距離進行。
- 從優先順序佇列中彈出距離最小的頂點（首先彈出的頂點=源點）。
- 如果“當前頂點距離 + 邊權重 < 下一個頂點距離”，則更新與彈出頂點相連的頂點的距離，然後將具有新距離的頂點壓入優先順序佇列。
- 如果之前已訪問過彈出頂點，則只需繼續，無需使用它。
- 重複執行相同的演算法，直到優先順序佇列為空。
給定一個圖和圖中的源頂點，查詢從源點到給定圖中所有頂點的最短路徑。給定圖的權重矩陣G[][]，圖中頂點的數量n，起始節點u。
輸入
G[max][max]={{0,1,0,3,10},
{1,0,5,0,0},
{0,5,0,2,1},
{3,0,2,0,6},
{10,0,1,6,0}}
n=5
u=0輸出
Distance of node1=1 Path=1<-0 Distance of node2=5 Path=2<-3<-0 Distance of node3=3 Path=3<-0 Distance of node4=6 Path=4<-2<-3<-0
解釋
從鄰接矩陣adj[ ][ ]建立代價矩陣C[ ][ ]。C[i][j]是從頂點i到頂點j的代價。如果頂點i和j之間沒有邊，則C[i][j]為無窮大。
陣列visited[ ]初始化為零。
for(i=0;i<n;i++) visited[i]=0;
如果頂點0是源頂點，則將visited[0]標記為1。
建立距離矩陣，儲存從源頂點0到頂點0到n-1的代價。
for(i=1;i<n;i++) distance[i]=cost[0][i];
最初，源頂點的距離取為0，即distance[0]=0;
for(i=1;i<n;i++) visited[i]=0;
選擇一個頂點w，使得distance[w]最小且visited[w]為0。將visited[w]標記為1。
重新計算從源點到剩餘頂點的最短距離。
只有陣列visited[ ]中未標記為1的頂點才應考慮重新計算距離。即對於每個頂點v
if(visited[v]==0) distance[v]=min(distance[v], distance[w]+cost[w][v])
示例
#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
int n=5;
int u=0;
dijkstra(G,n,u);
return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
int cost[max][max],distance[max],pred[max];
int visited[max],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
for(i=0;i<n;i++) {
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1) {
mindistance=INFINITY;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i]) {
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i]) {
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=startnode) {
cout<<"\nDistance of node"<<i<<"="<<distance[i];
cout<<"\nPath="<<i;
j=i;
do {
j=pred[j];
cout<<"<-"<<j;
}while(j!=startnode);
}
}
更新於：2019年8月9日
15K+ 次瀏覽
廣告