Camino más largo en un gráfico acíclico dirigido | Conjunto 2
Dado un gráfico acíclico dirigido ponderado (DAG) y un vértice de origen en él, encuentre las distancias más largas desde el vértice de origen a todos los demás vértices en el gráfico dado.
Ya hemos comentado cómo podemos encontrar Ruta más larga en gráfico acíclico dirigido (DAG) en el Conjunto 1. En esta publicación discutiremos otra solución interesante para encontrar la ruta más larga de DAG que utiliza un algoritmo para encontrar Ruta más corta en un DAG .
La idea es negar los pesos del camino y encontrar el camino más corto en el gráfico . Un camino más largo entre dos vértices s y t dados en un gráfico ponderado G es lo mismo que un camino más corto en un gráfico G' derivado de G cambiando cada peso a su negación. Por lo tanto, si los caminos más cortos se pueden encontrar en G', entonces los caminos más largos también se pueden encontrar en G.
A continuación se muestra el proceso paso a paso para encontrar caminos más largos:
Cambiamos el peso de cada borde de un gráfico dado a su negación e inicializamos las distancias a todos los vértices como infinitas y la distancia a la fuente como 0, luego encontramos una clasificación topológica del gráfico que representa un orden lineal del gráfico. Cuando consideramos un vértice u en orden topológico, se garantiza que hemos considerado todas las aristas entrantes. es decir, ya hemos encontrado la ruta más corta a ese vértice y podemos usar esa información para actualizar la ruta más corta de todos sus vértices adyacentes. Una vez que tenemos el orden topológico, procesamos uno por uno todos los vértices en orden topológico. Para cada vértice que se procesa, actualizamos las distancias de su vértice adyacente utilizando la distancia más corta del vértice actual desde el vértice de origen y su peso de borde. es decir.
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)
Una vez que hayamos encontrado todos los caminos más cortos desde el vértice de origen, los caminos más largos serán simplemente la negación de los caminos más cortos.
A continuación se muestra la implementación del enfoque anterior:
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
Producción
Following are longest distances from source vertex 1 INT_MIN 0 2 9 8 10
Complejidad del tiempo : La complejidad temporal de la clasificación topológica es O(V+E). Después de encontrar el orden topológico, el algoritmo procesa todos los vértices y para cada vértice ejecuta un bucle para todos los vértices adyacentes. Como el total de vértices adyacentes en un gráfico es O (E), el bucle interno se ejecuta O (V + E) veces. Por lo tanto, la complejidad temporal general de este algoritmo es O (V + E).
Complejidad espacial:
La complejidad espacial del algoritmo anterior es O(V). Estamos almacenando la matriz de salida y una pila para clasificación topológica.
