가중치가 있는 방향성 비순환 그래프(DAG)와 그 안에 있는 소스 정점이 주어지면 주어진 그래프의 소스 정점에서 다른 모든 정점까지의 가장 긴 거리를 찾습니다.
우리는 이미 어떻게 찾을 수 있는지 논의했습니다. 방향성 비순환 그래프(DAG)의 최장 경로 세트 1. 이 게시물에서는 알고리즘을 사용하여 DAG의 가장 긴 경로를 찾는 또 다른 흥미로운 솔루션에 대해 논의하겠습니다. DAG의 최단 경로 .
아이디어는 경로의 가중치를 무효화하고 그래프에서 최단 경로를 찾습니다. . 가중치 그래프 G에서 주어진 두 정점 s와 t 사이의 최장 경로는 모든 가중치를 부정으로 변경하여 G에서 파생된 그래프 G'의 최단 경로와 동일합니다. 따라서 G'에서 최단 경로를 찾을 수 있으면 G에서도 가장 긴 경로를 찾을 수 있습니다.
다음은 가장 긴 경로를 찾는 단계별 과정입니다.
수학.랜덤 자바
주어진 그래프의 모든 가장자리의 가중치를 부정으로 변경하고 모든 정점까지의 거리를 무한대로, 소스까지의 거리를 0으로 초기화한 다음 그래프의 선형 순서를 나타내는 그래프의 토폴로지 정렬을 찾습니다. 정점 u를 토폴로지 순서로 고려할 때 모든 들어오는 가장자리를 고려했음이 보장됩니다. 즉, 우리는 이미 해당 정점에 대한 최단 경로를 찾았으며 해당 정보를 사용하여 모든 인접한 정점의 더 짧은 경로를 업데이트할 수 있습니다. 토폴로지 순서가 있으면 모든 정점을 토폴로지 순서로 하나씩 처리합니다. 처리되는 모든 정점에 대해 소스 정점과 가장자리 가중치에서 현재 정점의 최단 거리를 사용하여 인접한 정점의 거리를 업데이트합니다. 즉.
for every adjacent vertex v of every vertex u in topological order if (dist[v] > dist[u] + weight(u v)) dist[v] = dist[u] + weight(u v)
소스 정점에서 가장 짧은 경로를 모두 찾으면 가장 긴 경로는 최단 경로를 부정하는 것입니다.
다음은 위의 접근 방식을 구현한 것입니다.
컴퓨터가 발명된 해C++
// A C++ program to find single source longest distances // in a DAG #include
# A Python3 program to find single source # longest distances in a DAG import sys def addEdge(u v w): global adj adj[u].append([v w]) # A recursive function used by longestPath. # See below link for details. # https:#www.geeksforgeeks.org/topological-sorting/ def longestPathUtil(v): global visited adjStack visited[v] = 1 # Recur for all the vertices adjacent # to this vertex for node in adj[v]: if (not visited[node[0]]): longestPathUtil(node[0]) # Push current vertex to stack which # stores topological sort Stack.append(v) # The function do Topological Sort and finds # longest distances from given source vertex def longestPath(s): # Initialize distances to all vertices # as infinite and global visited Stack adjV dist = [sys.maxsize for i in range(V)] # for (i = 0 i < V i++) # dist[i] = INT_MAX dist[s] = 0 for i in range(V): if (visited[i] == 0): longestPathUtil(i) # print(Stack) while (len(Stack) > 0): # Get the next vertex from topological order u = Stack[-1] del Stack[-1] if (dist[u] != sys.maxsize): # Update distances of all adjacent vertices # (edge from u -> v exists) for v in adj[u]: # Consider negative weight of edges and # find shortest path if (dist[v[0]] > dist[u] + v[1] * -1): dist[v[0]] = dist[u] + v[1] * -1 # Print the calculated longest distances for i in range(V): if (dist[i] == sys.maxsize): print('INT_MIN ' end = ' ') else: print(dist[i] * (-1) end = ' ') # Driver code if __name__ == '__main__': V = 6 visited = [0 for i in range(7)] Stack = [] adj = [[] for i in range(7)] addEdge(0 1 5) addEdge(0 2 3) addEdge(1 3 6) addEdge(1 2 2) addEdge(2 4 4) addEdge(2 5 2) addEdge(2 3 7) addEdge(3 5 1) addEdge(3 4 -1) addEdge(4 5 -2) s = 1 print('Following are longest distances from source vertex' s) longestPath(s) # This code is contributed by mohit kumar 29
// C# program to find single source longest distances // in a DAG using System; using System.Collections.Generic; // Graph is represented using adjacency list. Every node of // adjacency list contains vertex number of the vertex to // which edge connects. It also contains weight of the edge class AdjListNode { private int v; private int weight; public AdjListNode(int _v int _w) { v = _v; weight = _w; } public int getV() { return v; } public int getWeight() { return weight; } } // Graph class represents a directed graph using adjacency // list representation class Graph { private int V; // No. of vertices // Pointer to an array containing adjacency lists private List<AdjListNode>[] adj; public Graph(int v) // Constructor { V = v; adj = new List<AdjListNode>[ v ]; for (int i = 0; i < v; i++) adj[i] = new List<AdjListNode>(); } public void AddEdge(int u int v int weight) { AdjListNode node = new AdjListNode(v weight); adj[u].Add(node); // Add v to u's list } // A recursive function used by longestPath. See below // link for details. // https://www.geeksforgeeks.org/dsa/topological-sorting/ private void LongestPathUtil(int v bool[] visited Stack<int> stack) { // Mark the current node as visited visited[v] = true; // Recur for all the vertices adjacent to this // vertex foreach(AdjListNode node in adj[v]) { if (!visited[node.getV()]) LongestPathUtil(node.getV() visited stack); } // Push current vertex to stack which stores // topological sort stack.Push(v); } // The function do Topological Sort and finds longest // distances from given source vertex public void LongestPath(int s) { // Initialize distances to all vertices as infinite // and distance to source as 0 int[] dist = new int[V]; for (int i = 0; i < V; i++) dist[i] = Int32.MaxValue; dist[s] = 0; Stack<int> stack = new Stack<int>(); // Mark all the vertices as not visited bool[] visited = new bool[V]; for (int i = 0; i < V; i++) { if (visited[i] == false) LongestPathUtil(i visited stack); } // Process vertices in topological order while (stack.Count > 0) { // Get the next vertex from topological order int u = stack.Pop(); if (dist[u] != Int32.MaxValue) { // Update distances of all adjacent vertices // (edge from u -> v exists) foreach(AdjListNode v in adj[u]) { // consider negative weight of edges and // find shortest path if (dist[v.getV()] > dist[u] + v.getWeight() * -1) dist[v.getV()] = dist[u] + v.getWeight() * -1; } } } // Print the calculated longest distances for (int i = 0; i < V; i++) { if (dist[i] == Int32.MaxValue) Console.Write('INT_MIN '); else Console.Write('{0} ' dist[i] * -1); } Console.WriteLine(); } } public class GFG { // Driver code static void Main(string[] args) { Graph g = new Graph(6); g.AddEdge(0 1 5); g.AddEdge(0 2 3); g.AddEdge(1 3 6); g.AddEdge(1 2 2); g.AddEdge(2 4 4); g.AddEdge(2 5 2); g.AddEdge(2 3 7); g.AddEdge(3 5 1); g.AddEdge(3 4 -1); g.AddEdge(4 5 -2); int s = 1; Console.WriteLine( 'Following are longest distances from source vertex {0} ' s); g.LongestPath(s); } } // This code is contributed by cavi4762.
// A Java program to find single source longest distances // in a DAG import java.util.*; // Graph is represented using adjacency list. Every // node of adjacency list contains vertex number of // the vertex to which edge connects. It also // contains weight of the edge class AdjListNode { private int v; private int weight; AdjListNode(int _v int _w) { v = _v; weight = _w; } int getV() { return v; } int getWeight() { return weight; } } // Class to represent a graph using adjacency list // representation public class GFG { int V; // No. of vertices' // Pointer to an array containing adjacency lists ArrayList<AdjListNode>[] adj; @SuppressWarnings('unchecked') GFG(int V) // Constructor { this.V = V; adj = new ArrayList[V]; for (int i = 0; i < V; i++) { adj[i] = new ArrayList<>(); } } void addEdge(int u int v int weight) { AdjListNode node = new AdjListNode(v weight); adj[u].add(node); // Add v to u's list } // A recursive function used by longestPath. See // below link for details https:// // www.geeksforgeeks.org/topological-sorting/ void topologicalSortUtil(int v boolean visited[] Stack<Integer> stack) { // Mark the current node as visited visited[v] = true; // Recur for all the vertices adjacent to this // vertex for (int i = 0; i < adj[v].size(); i++) { AdjListNode node = adj[v].get(i); if (!visited[node.getV()]) topologicalSortUtil(node.getV() visited stack); } // Push current vertex to stack which stores // topological sort stack.push(v); } // The function to find Smallest distances from a // given vertex. It uses recursive // topologicalSortUtil() to get topological sorting. void longestPath(int s) { Stack<Integer> stack = new Stack<Integer>(); int dist[] = new int[V]; // Mark all the vertices as not visited boolean visited[] = new boolean[V]; for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to store // Topological Sort starting from all vertices // one by one for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortUtil(i visited stack); // Initialize distances to all vertices as // infinite and distance to source as 0 for (int i = 0; i < V; i++) dist[i] = Integer.MAX_VALUE; dist[s] = 0; // Process vertices in topological order while (stack.isEmpty() == false) { // Get the next vertex from topological // order int u = stack.peek(); stack.pop(); // Update distances of all adjacent vertices if (dist[u] != Integer.MAX_VALUE) { for (AdjListNode v : adj[u]) { if (dist[v.getV()] > dist[u] + v.getWeight() * -1) dist[v.getV()] = dist[u] + v.getWeight() * -1; } } } // Print the calculated longest distances for (int i = 0; i < V; i++) if (dist[i] == Integer.MAX_VALUE) System.out.print('INF '); else System.out.print(dist[i] * -1 + ' '); } // Driver program to test above functions public static void main(String args[]) { // Create a graph given in the above diagram. // Here vertex numbers are 0 1 2 3 4 5 with // following mappings: // 0=r 1=s 2=t 3=x 4=y 5=z GFG g = new GFG(6); g.addEdge(0 1 5); g.addEdge(0 2 3); g.addEdge(1 3 6); g.addEdge(1 2 2); g.addEdge(2 4 4); g.addEdge(2 5 2); g.addEdge(2 3 7); g.addEdge(3 5 1); g.addEdge(3 4 -1); g.addEdge(4 5 -2); int s = 1; System.out.print( 'Following are longest distances from source vertex ' + s + ' n'); g.longestPath(s); } } // This code is contributed by Prithi_Dey
class AdjListNode { constructor(v weight) { this.v = v; this.weight = weight; } getV() { return this.v; } getWeight() { return this.weight; } } class GFG { constructor(V) { this.V = V; this.adj = new Array(V); for (let i = 0; i < V; i++) { this.adj[i] = new Array(); } } addEdge(u v weight) { let node = new AdjListNode(v weight); this.adj[u].push(node); } topologicalSortUtil(v visited stack) { visited[v] = true; for (let i = 0; i < this.adj[v].length; i++) { let node = this.adj[v][i]; if (!visited[node.getV()]) { this.topologicalSortUtil(node.getV() visited stack); } } stack.push(v); } longestPath(s) { let stack = new Array(); let dist = new Array(this.V); let visited = new Array(this.V); for (let i = 0; i < this.V; i++) { visited[i] = false; } for (let i = 0; i < this.V; i++) { if (!visited[i]) { this.topologicalSortUtil(i visited stack); } } for (let i = 0; i < this.V; i++) { dist[i] = Number.MAX_SAFE_INTEGER; } dist[s] = 0; let u = stack.pop(); while (stack.length > 0) { u = stack.pop(); if (dist[u] !== Number.MAX_SAFE_INTEGER) { for (let v of this.adj[u]) { if (dist[v.getV()] > dist[u] + v.getWeight() * -1) { dist[v.getV()] = dist[u] + v.getWeight() * -1; } } } } for (let i = 0; i < this.V; i++) { if (dist[i] === Number.MAX_SAFE_INTEGER) { console.log('INF'); } else { console.log(dist[i] * -1); } } } } let g = new GFG(6); g.addEdge(0 1 5); g.addEdge(0 2 3); g.addEdge(1 3 6); g.addEdge(1 2 2); g.addEdge(2 4 4); g.addEdge(2 5 2); g.addEdge(2 3 7); g.addEdge(3 5 1); g.addEdge(3 4 -1); g.addEdge(4 5 -2); console.log('Longest distances from the vertex 1 : '); g.longestPath(1); //this code is contributed by devendra
산출
Following are longest distances from source vertex 1 INT_MIN 0 2 9 8 10
시간 복잡도 : 위상 정렬의 시간 복잡도는 O(V + E). 위상 순서를 찾은 후 알고리즘은 모든 정점을 처리하고 모든 정점에 대해 모든 인접한 정점에 대해 루프를 실행합니다. 그래프의 총 인접 꼭지점은 O(E)이므로 내부 루프는 O(V + E) 번 실행됩니다. 따라서 이 알고리즘의 전체 시간 복잡도는 O(V + E)입니다.
공간 복잡도:
위 알고리즘의 공간 복잡도는 다음과 같습니다. 오(V). 위상 정렬을 위해 출력 배열과 스택을 저장하고 있습니다.