Dado un gráfico cíclico dirigido ponderado ( DAG ) y un vértice fuente en él, encuentre las distancias más largas desde s hasta todos los demás vértices en el gráfico dado.
El problema de la ruta más larga para un gráfico general no es tan fácil como el problema de la ruta más corta porque el problema de la ruta más larga no tiene una propiedad de subestructura óptima . De hecho, el problema de la ruta más larga es NP-Hard para un gráfico general . Sin embargo, el problema del camino más largo tiene una solución de tiempo lineal para gráficos acíclicos dirigidos. La idea es similar a la solución de tiempo lineal para el camino más corto en un gráfico acíclico dirigido. , usamos Clasificación Topológica .
Inicializamos las distancias a todos los vértices como menos infinito y la distancia a la fuente como 0, luego encontramos una clasificación topológica del gráfico. La clasificación topológica de un gráfico representa una ordenación lineal del gráfico (consulte a continuación, la figura (b) es una representación lineal de la figura (a)). Una vez que tenemos el orden topológico (o representación lineal), procesamos uno por uno todos los vértices en orden topológico. Para cada vértice que se procesa, actualizamos las distancias de sus adyacentes usando la distancia del vértice actual.
La siguiente figura muestra el proceso paso a paso para encontrar los caminos más largos.
El siguiente es un algoritmo completo para encontrar las distancias más largas.
- Inicialice dist[] = {NINF, NINF, ….} y dist[s] = 0 donde s es el vértice de origen. Aquí NINF significa infinito negativo.
- Crea un orden topológico de todos los vértices.
- Haz lo siguiente para cada vértice u en orden topológico.
- ..Hacer lo siguiente para cada vértice adyacente v de u
- ……si (dist[v] < dist[u] + peso(u, v))
- ………dist[v] = dist[u] + peso(u, v)
A continuación se muestra la implementación en C++ del algoritmo anterior.
CPP
// A C++ program to find single source longest distances
// in a DAG
#include <iostream>
#include <limits.h>
#include <list>
#include <stack>
#define NINF INT_MIN
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; }
};
// Class to represent a graph using adjacency list
// representation
class Graph {
int V; // No. of vertices'
// Pointer to an array containing adjacency lists
list<AdjListNode>* adj;
// A function used by longestPath
void topologicalSortUtil(int v, bool visited[],
stack<int>& Stack);
public:
Graph(int V); // Constructor
~Graph(); // Destructor
// function to add an edge to graph
void addEdge(int u, int v, int weight);
// Finds longest distances from given source vertex
void longestPath(int s);
};
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::topologicalSortUtil(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
list<AdjListNode>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i) {
AdjListNode node = *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 longest distances from a given vertex.
// It uses recursive topologicalSortUtil() to get topological
// sorting.
void Graph::longestPath(int s)
{
stack<int> Stack;
int dist[V];
// Mark all the vertices as not visited
bool* visited = new bool[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] = NINF;
dist[s] = 0;
// Process vertices in topological order
while (Stack.empty() == false) {
// Get the next vertex from topological order
int u = Stack.top();
Stack.pop();
// Update distances of all adjacent vertices
list<AdjListNode>::iterator i;
if (dist[u] != NINF) {
for (i = adj[u].begin(); i != adj[u].end(); ++i){
if (dist[i->getV()] < dist[u] + i->getWeight())
dist[i->getV()] = dist[u] + i->getWeight();
}
}
}
// Print the calculated longest distances
for (int i = 0; i < V; i++)
(dist[i] == NINF) ? cout << "INF " : cout << dist[i] << " ";
delete [] visited;
}
// Driver program to test above functions
int main()
{
// 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
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;
}
Java
// A Java program to find single source longest distances
// in a DAG
import java.util.*;
class GFG
{
// 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
static class AdjListNode {
int v;
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
static class Graph {
int V; // No. of vertices'
// Pointer to an array containing adjacency lists
ArrayList<ArrayList<AdjListNode>> adj;
Graph(int V) // Constructor
{
this.V = V;
adj = new ArrayList<ArrayList<AdjListNode>>(V);
for(int i = 0; i < V; i++){
adj.add(new ArrayList<AdjListNode>());
}
}
void addEdge(int u, int v, int weight)
{
AdjListNode node = new AdjListNode(v, weight);
adj.get(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.get(v).size(); i++) {
AdjListNode node = adj.get(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 longest 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.MIN_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.MIN_VALUE)
{
for (int i = 0; i<adj.get(u).size(); i++)
{
AdjListNode node = adj.get(u).get(i);
if (dist[node.getV()] < dist[u] + node.getWeight())
dist[node.getV()] = dist[u] + node.getWeight();
}
}
}
// Print the calculated longest distances
for (int i = 0; i < V; i++)
if(dist[i] == Integer.MIN_VALUE)
System.out.print("INF ");
else
System.out.print(dist[i] + " ");
}
}
// 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
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;
System.out.print("Following are longest distances from source vertex "+ s + " \n" );
g.longestPath(s);
}
}
// This code is contribute by adityapande88.
Python3
# A recursive function used by longestPath. See below
# link for details
# https:#www.geeksforgeeks.org/topological-sorting/
def topologicalSortUtil(v):
global Stack, visited, adj
visited[v] = True
# Recur for all the vertices adjacent to this vertex
# list<AdjListNode>::iterator i
for i in adj[v]:
if (not visited[i[0]]):
topologicalSortUtil(i[0])
# Push current vertex to stack which stores topological
# sort
Stack.append(v)
# The function to find longest distances from a given vertex.
# It uses recursive topologicalSortUtil() to get topological
# sorting.
def longestPath(s):
global Stack, visited, adj, V
dist = [-10**9 for i in range(V)]
# Call the recursive helper function to store Topological
# Sort starting from all vertices one by one
for i in range(V):
if (visited[i] == False):
topologicalSortUtil(i)
# print(Stack)
# Initialize distances to all vertices as infinite and
# distance to source as 0
dist[s] = 0
# Stack.append(1)
# Process vertices in topological order
while (len(Stack) > 0):
# Get the next vertex from topological order
u = Stack[-1]
del Stack[-1]
#print(u)
# Update distances of all adjacent vertices
# list<AdjListNode>::iterator i
if (dist[u] != 10**9):
for i in adj[u]:
# print(u, i)
if (dist[i[0]] < dist[u] + i[1]):
dist[i[0]] = dist[u] + i[1]
# Print calculated longest distances
# print(dist)
for i in range(V):
print("INF ",end="") if (dist[i] == -10**9) else print(dist[i],end=" ")
# Driver code
if __name__ == '__main__':
V, Stack, visited = 6, [], [False for i in range(7)]
adj = [[] for i in range(7)]
# 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
adj[0].append([1, 5])
adj[0].append([2, 3])
adj[1].append([3, 6])
adj[1].append([2, 2])
adj[2].append([4, 4])
adj[2].append([5, 2])
adj[2].append([3, 7])
adj[3].append([5, 1])
adj[3].append([4, -1])
adj[4].append([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; }
}
// Class to represent a 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
{
this.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 TopologicalSortUtil(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
for (int i = 0; i < adj[v].Count; i++) {
AdjListNode node = adj[v][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 longest distances from a given
// vertex. It uses recursive topologicalSortUtil() to
// get topological sorting.
public void LongestPath(int s)
{
Stack<int> stack = new Stack<int>();
int[] dist = new int[V];
// Mark all the vertices as not visited
bool[] visited = new bool[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] = Int32.MinValue;
dist[s] = 0;
// Process vertices in topological order
while (stack.Count > 0) {
// Get the next vertex from topological order
int u = stack.Pop();
// Update distances of all adjacent vertices ;
if (dist[u] != Int32.MinValue) {
for (int i = 0; i < adj[u].Count; i++) {
AdjListNode node = adj[u][i];
if (dist[node.getV()]
< dist[u] + node.getWeight())
dist[node.getV()]
= dist[u] + node.getWeight();
}
}
}
// Print the calculated longest distances
for (int i = 0; i < V; i++) {
if (dist[i] == Int32.MinValue)
Console.Write("INF ");
else
Console.Write(dist[i] + " ");
}
Console.WriteLine();
}
}
public class GFG {
// Driver program to test above functions
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
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
Producción
Following are longest distances from source vertex 1 INF 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. El total de vértices adyacentes en un gráfico es O(E). Entonces, el bucle interno se ejecuta O (V + E) veces. Por lo tanto, la complejidad temporal total de este algoritmo es O(V+E).
Ejercicio: la solución anterior imprime las distancias más largas, extienda el código para imprimir también las rutas.
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