가중된 방향성 비순환 그래프 하나가 제공됩니다. 다른 소스 정점도 제공됩니다. 이제 그래프에서 시작 노드에서 다른 모든 정점까지의 가장 긴 거리를 찾아야 합니다.
토폴로지 정렬 기법으로 노드를 정렬해야 하며, 토폴로지 정렬 후 결과는 스택에 저장됩니다. 그 후 스택에서 반복적으로 팝되고 각 정점에 대한 가장 긴 거리를 찾습니다.
입력 및 출력
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, 방문, 스택)
입력: 시작 노드 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
longestPath(시작)
입력 - 시작 노드.
출력 - 시작 노드에서 모든 정점의 가장 긴 거리의 목록입니다.
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