資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學有向無環圖中的最短路徑
給定一個加權有向無環圖和一個源頂點。現在需要找到從起始節點到圖中所有其他頂點的最短距離。
為了檢測更短的距離，我們可以使用其他演算法，例如對於帶負權重的圖使用Bellman-Ford演算法，對於正權重，Dijkstra演算法也很有用。在這裡，對於有向無環圖，我們將使用拓撲排序技術來降低複雜度。
輸入和輸出
Input: The cost matrix of the graph. 0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ -∞ -∞ 0 -1 1 -∞ -∞ -∞ -∞ 0 -2 -∞ -∞ -∞ -∞ -∞ 0 Output: Shortest Distance from Source Vertex 1 Infinity 0 2 6 5 3
演算法
topoSort(u, visited, stack)
輸入：起始節點u，用於跟蹤的已訪問列表，堆疊。
輸出：以拓撲方式對節點進行排序。
Begin mark u as visited for all vertex v, which is connected with u, do if v is not visited, then topoSort(v, visited, stack) done push u into the stack End
shortestPath(start)
輸入：起始節點。
輸出：從起始節點到所有頂點的最短距離列表。
Begin initially make all nodes as unvisited for each node i, in the graph, do if i is not visited, then topoSort(i, visited, stack) done make distance of all vertices as ∞ dist[start] := 0 while stack is not empty, do pop stack item and take into nextVert if dist[nextVert] ≠∞, then for each vertices v, which is adjacent with nextVert, do if cost[nextVert, v] ≠∞, then if dist[v] > dist[nectVert] + cost[nextVert, v], then dist[v] := dist[nectVert] + cost[nextVert, v] done done for all vertices i in the graph, do if dist[i] = ∞, then display Infinity else display dist[i] done End
示例
#include<iostream>
#include<stack>
#define NODE 6
#define INF 9999
using namespace std;
int cost[NODE][NODE] = {
{0, 5, 3, INF, INF, INF},
{INF, 0, 2, 6, INF, INF},
{INF, INF, 0, 7, 4, 2},
{INF, INF, INF, 0, -1, 1},
{INF, INF, INF, INF, 0, -2},
{INF, INF, INF, INF, INF, 0}
};
void topoSort(int u, bool visited[], stack<int>&stk) {
visited[u] = true; //set as the node v is visited
for(int v = 0; v<NODE; v++) {
if(cost[u][v]) { //for allvertices v adjacent to u
if(!visited[v])
topoSort(v, visited, stk);
}
}
stk.push(u); //push starting vertex into the stack
}
void shortestPath(int start) {
stack<int> stk;
int dist[NODE];
bool vis[NODE];
for(int i = 0; i<NODE;i++)
vis[i] = false; // make all nodes as unvisited at first
for(int i = 0; i<NODE; i++) //perform topological sort for vertices
if(!vis[i])
topoSort(i, vis, stk);
for(int i = 0; i<NODE; i++)
dist[i] = INF; //initially all distances are infinity
dist[start] = 0; //distance for start vertex is 0
while(!stk.empty()) { //when stack contains element, process in topological order
int nextVert = stk.top(); stk.pop();
if(dist[nextVert] != INF) {
for(int v = 0; v<NODE; v++) {
if(cost[nextVert][v] && cost[nextVert][v] != INF){ if(dist[v] > dist[nextVert] +cost[nextVert][v])dist[v] = dist[nextVert] + cost[nextVert][v];
}
}
}
for(int i = 0; i<NODE; i++)
(dist[i] == INF)?cout << "Infinity ":cout << dist[i]<<" ";
}
main() {
int start = 1;
cout << "Shortest Distance From Source Vertex "<<start<<endl;
shortestPath(start);
}輸出
Shortest Distance From Source Vertex 1 Infinity 0 2 6 5 3
更新於：2020年6月16日
1K+ 次瀏覽
廣告