Garākais ceļš virzītā acikliskā diagrammā | 2. komplekts
Ņemot vērā svērto virzīto aciklisko grafiku (DAG) un tajā esošo avota virsotni, atrodiet garākos attālumus no avota virsotnes līdz visām pārējām virsotnēm dotajā grafikā.
Mēs jau esam apsprieduši, kā mēs varam atrast Garākais ceļš virzītā acikliskā diagrammā (DAG) 1. komplektā. Šajā rakstā mēs apspriedīsim vēl vienu interesantu risinājumu, lai atrastu garāko DAG ceļu, kas izmanto algoritmu meklēšanai Īsākais ceļš DAG .
Ideja ir, lai noliegt ceļa svarus un grafikā atrast īsāko ceļu . Garākais ceļš starp divām dotajām virsotnēm s un t svērtā grafā G ir tas pats, kas īsākais ceļš grafā G', kas iegūts no G, mainot katru svaru uz tā noliegumu. Tāpēc, ja īsākos ceļus var atrast G, tad garākos ceļus var atrast arī G.
Tālāk ir sniegts soli pa solim garāko ceļu atrašanas process -
Mēs mainām katras dotā grafa malas svaru uz tās noliegumu un inicializējam attālumus līdz visām virsotnēm kā bezgalīgus un attālumu līdz avotam kā 0, tad mēs atrodam grafa topoloģisku šķirošanu, kas attēlo lineāru grafiku. Aplūkojot virsotni u topoloģiskā secībā, tiek garantēts, ka esam ņēmuši vērā katru tai ienākošo malu. i., mēs jau esam atraduši īsāko ceļu uz šo virsotni, un mēs varam izmantot šo informāciju, lai atjauninātu visu tai blakus esošo virsotņu īsāko ceļu. Kad mums ir topoloģiskā secība, mēs pa vienam apstrādājam visas virsotnes topoloģiskā secībā. Katrai apstrādātajai virsotnei mēs atjauninām tās blakus esošās virsotnes attālumus, izmantojot pašreizējās virsotnes īsāko attālumu no avota virsotnes un tās malas svaru. t.i.
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)
Kad esam atraduši visus īsākos ceļus no avota virsotnes, garākie ceļi būs tikai īsāko ceļu noliegums.
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
C++ // A C++ program to find single source longest distances // in a DAG #include using namespace std ; // 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 { int v ; int weight ; public : AdjListNode ( int _v int _w ) { v = _v ; weight = _w ; } int getV () { return v ; } int getWeight () { return weight ; } }; // Graph class represents a directed graph using adjacency // list representation class Graph { int V ; // No. of vertices // Pointer to an array containing adjacency lists list < AdjListNode >* adj ; // This function uses DFS void longestPathUtil ( int vector < bool > & stack < int > & ); public : Graph ( int ); // Constructor ~ Graph (); // Destructor // function to add an edge to graph void addEdge ( int int int ); void longestPath ( int ); }; Graph :: Graph ( int V ) // Constructor { this -> V = V ; adj = new list < AdjListNode > [ V ]; } Graph ::~ Graph () // Destructor { delete [] adj ; } void Graph :: addEdge ( int u int v int weight ) { AdjListNode node ( v weight ); adj [ u ]. push_back ( 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/ void Graph :: longestPathUtil ( int v vector < bool > & visited stack < int > & Stack ) { // Mark the current node as visited visited [ v ] = true ; // Recur for all the vertices adjacent to this vertex for ( AdjListNode node : 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 void Graph :: longestPath ( int s ) { // Initialize distances to all vertices as infinite and // distance to source as 0 int dist [ V ]; for ( int i = 0 ; i < V ; i ++ ) dist [ i ] = INT_MAX ; dist [ s ] = 0 ; stack < int > Stack ; // Mark all the vertices as not visited vector < bool > visited ( V false ); for ( int i = 0 ; i < V ; i ++ ) if ( visited [ i ] == false ) longestPathUtil ( i visited Stack ); // Process vertices in topological order while ( ! Stack . empty ()) { // Get the next vertex from topological order int u = Stack . top (); Stack . pop (); if ( dist [ u ] != INT_MAX ) { // Update distances of all adjacent vertices // (edge from u -> v exists) for ( AdjListNode v : 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 ] == INT_MAX ) cout < < 'INT_MIN ' ; else cout < < ( dist [ i ] * -1 ) < < ' ' ; } } // Driver code int main () { Graph g ( 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 ; cout < < 'Following are longest distances from ' < < 'source vertex ' < < s < < ' n ' ; g . longestPath ( s ); return 0 ; }
Python3 # 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 adj Stack 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 adj V 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# // 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.
Java // 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
JavaScript 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
Izvade
Following are longest distances from source vertex 1 INT_MIN 0 2 9 8 10
Laika sarežģītība : Topoloģiskās šķirošanas laika sarežģītība ir O(V+E). Pēc topoloģiskās secības noteikšanas algoritms apstrādā visas virsotnes un katrai virsotnei veic cilpu visām blakus esošajām virsotnēm. Tā kā kopējās blakus esošās virsotnes grafā ir O(E), iekšējā cilpa darbojas O(V + E) reizes. Tāpēc šī algoritma kopējā laika sarežģītība ir O(V + E).
Kosmosa sarežģītība:
Iepriekš minētā algoritma telpas sarežģītība ir O(V). Mēs glabājam izvades masīvu un kaudzīti topoloģiskai šķirošanai.
