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 hasta todos los demás vértices en el gráfico dado.
Ya hemos discutido cómo podemos encontrar la ruta más larga en el 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 usa un algoritmo para encontrar la 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 dados s y t 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 los caminos más largos:
Cambiamos el peso de cada borde del gráfico dado a su negación e inicializamos las distancias a todos los vértices como infinito y la distancia a la fuente como 0, luego encontramos una clasificación topológica del gráfico que representa un ordenamiento 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 usando 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 <bits/stdc++.h>
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/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/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.
Following are longest distances from source vertex 1 INT_MIN 0 2 9 8 10
Complejidad de tiempo : la complejidad de tiempo 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 ciclo interno se ejecuta O(V + E) veces. Por lo tanto, la complejidad temporal total de este algoritmo es O(V + E).
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA