資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究有向無環圖中的最長路徑
現給出一個帶權重的有向無環圖。另外還提供了一個源點。現在我們必須找出圖中起始節點到所有其他節點的最長距離。
我們需要用拓撲排序技術對節點進行排序，拓撲排序後的結果儲存到一個棧中。然後反覆從棧中 pop 出元素，並嘗試找出每個節點的最長距離。
輸入和輸出
Input: The cost matrix of the graph. 0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ -∞ -∞ 0 -1 1 -∞ -∞ -∞ -∞ 0 -2 -∞ -∞ -∞ -∞ -∞ 0 Output: Longest Distance from Source Vertex 1 Infinity 0 2 9 8 10
演算法
topoSort(u, visited, stack)
輸入：起始節點 u，用於跟蹤的 visited 列表，棧。
輸出 −按拓撲方式對節點進行排序。
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
longestPath(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 longestPath(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 << "Longest Distance From Source Vertex "<<start<<endl;
longestPath(start);
}輸出
Longest Distance From Source Vertex 1 Infinity 0 2 9 8 10
更新時間： 2020-06-16
1K+ 檢視
廣告