資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究單源最短路徑，非負權重
單源最短路徑演算法（對於非負權重）也稱為 Dijkstra 演算法。給定一個圖 G(V,E) 及其鄰接矩陣表示，並提供一個源頂點。Dijkstra 演算法用於查詢從源頂點到圖 G 中任何其他頂點的最小最短路徑。
從起始節點到任何其他節點，找到最小的距離。在這個問題中，圖使用鄰接矩陣表示。（對於此目的，成本矩陣和鄰接矩陣是相似的）。
輸入 - 鄰接矩陣 -
0 3 6 ∞ ∞ ∞ ∞ 3 0 2 1 ∞ ∞ ∞ 6 2 0 1 4 2 ∞ ∞ 1 1 0 2 ∞ 4 ∞ ∞ 4 2 0 2 1 ∞ ∞ 2 ∞ 2 0 1 ∞ ∞ ∞ 4 1 1 0
輸出 -
0 to 1, Using: 0, Cost: 3 0 to 2, Using: 1, Cost: 5 0 to 3, Using: 1, Cost: 4 0 to 4, Using: 3, Cost: 6 0 to 5, Using: 2, Cost: 7 0 to 6, Using: 4, Cost: 7
演算法
dijkstraShortestPath(n, dist, next, start)
輸入 - 節點總數 n，每個頂點的距離列表，儲存下一個節點的 next 列表，以及種子或起始頂點。
輸出 - 從起始節點到所有其他頂點的最短路徑。
Begin create a status list to hold the current status of the selected node for all vertices u in V do status[u] := unconsidered dist[u] := distance from source using cost matrix next[u] := start done status[start] := considered, dist[start] := 0 and next[start] := φ while take unconsidered vertex u as distance is minimum do status[u] := considered for all vertex v in V do if status[v] = unconsidered then if dist[v] > dist[u] + cost[u,v] then dist[v] := dist[u] + cost[u,v] next[v] := u done done End
示例（C++）
#include<iostream>
#define V 7
#define INF 999
using namespace std;
//Cost matrix of the graph
int costMat[V][V] = {
{0, 3, 6, INF, INF, INF, INF},
{3, 0, 2, 1, INF, INF, INF},
{6, 2, 0, 1, 4, 2, INF},
{INF, 1, 1, 0, 2, INF, 4},
{INF, INF, 4, 2, 0, 2, 1},
{INF, INF, 2, INF, 2, 0, 1},
{INF, INF, INF, 4, 1, 1, 0}
};
int minimum(int *status, int *dis, int n){
int i, min, index;
min = INF;
for(i = 0; i<n; i++)
if(dis[i] < min && status[i] == 1){
min = dis[i];
index = i;
}
if(status[index] == 1)
return index;//minimum unconsidered vertex distance
else
return -1;//when all vertices considered
}
void dijkstra(int n, int *dist,int *next, int s){
int status[V];
int u, v;
//initialization
for(u = 0; u<n; u++){
status[u] = 1;//unconsidered vertex
dist[u] = costMat[u][s];//distance from source
next[u] = s;
}
//for source vertex
status[s] = 2; dist[s] = 0; next[s] = -1;//-1 for starting vertex
while((u = minimum(status, dist, n)) > -1){
status[u] = 2;//now considered
for(v = 0; v<n; v++)
if(status[v] == 1)
if(dist[v] > dist[u] + costMat[u][v]){
dist[v] = dist[u] + costMat[u][v];//update distance
next[v] = u;
}
}
}
main(){
int dis[V], next[V], i, start = 0;
dijkstra(V, dis, next, start);
for(i = 0; i<V; i++)
if(i != start)
cout << start << " to " << i <<", Using: " << next[i] << ", Cost: " << dis[i] << endl;
}輸出
0 to 1, Using: 0, Cost: 3 0 to 2, Using: 1, Cost: 5 0 to 3, Using: 1, Cost: 4 0 to 4, Using: 3, Cost: 6 0 to 5, Using: 2, Cost: 7 0 to 6, Using: 4, Cost: 7
更新於: 2020-07-02
725 次檢視
廣告