Dado un gráfico dirigido donde cada borde tiene un peso de 1 o 2, encuentre el camino más corto desde un vértice de origen dado ‘s’ hasta un vértice de destino dado ‘t’. La complejidad de tiempo esperada es O(V+E).
Una solución simple es usar el algoritmo de ruta más corta de Dijkstra , podemos obtener una ruta más corta en tiempo O (E + VLogV).
¿Cómo hacerlo en tiempo O(V+E)?
La idea es utilizar BFS . Una observación importante sobre BFS es que la ruta utilizada en BFS siempre tiene la menor cantidad de aristas entre dos vértices. Entonces, si todos los bordes tienen el mismo peso, podemos usar BFS para encontrar el camino más corto. Para este problema, podemos modificar el gráfico y dividir todos los bordes de peso 2 en dos bordes de peso 1 cada uno. En el gráfico modificado, podemos usar BFS para encontrar el camino más corto.
¿Cuántos nuevos vértices intermedios se necesitan?
Necesitamos agregar un nuevo vértice intermedio para cada vértice de origen. La razón es simple, si agregamos un vértice intermedio x entre u y v y si agregamos el mismo vértice entre y y z, entonces se agregan nuevos caminos u a z e y a v al gráfico que podría no haber estado allí en el gráfico original . Por tanto, en un grafo con V vértices, necesitamos V vértices extra. A continuación se muestra la implementación en C++ de la idea anterior. En la siguiente implementación, se crean vértices de 2*V en un gráfico y para cada borde (u, v), lo dividimos en dos bordes (u, u+V) y (u+V, w). De esta manera nos aseguramos de que se agregue un vértice intermedio diferente para cada vértice de origen.
Implementación:
C++
// Program to shortest path from a given source vertex ‘s’ to
// a given destination vertex ‘t’. Expected time complexity
// is O(V+E).
#include<bits/stdc++.h>
using namespace std;
// This class represents a directed graph using adjacency
// list representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w, int weight); // adds an edge
// finds shortest path from source vertex ‘s’ to
// destination vertex ‘d’.
int findShortestPath(int s, int d);
// print shortest path from a source vertex ‘s’ to
// destination vertex ‘d’.
int printShortestPath(int parent[], int s, int d);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[2*V];
}
void Graph::addEdge(int v, int w, int weight)
{
// split all edges of weight 2 into two
// edges of weight 1 each. The intermediate
// vertex number is maximum vertex number + 1,
// that is V.
if (weight==2)
{
adj[v].push_back(v+V);
adj[v+V].push_back(w);
}
else // Weight is 1
adj[v].push_back(w); // Add w to v’s list.
}
// To print the shortest path stored in parent[]
int Graph::printShortestPath(int parent[], int s, int d)
{
static int level = 0;
// If we reached root of shortest path tree
if (parent[s] == -1)
{
cout << "Shortest Path between " << s << " and "
<< d << " is " << s << " ";
return level;
}
printShortestPath(parent, parent[s], d);
level++;
if (s < V)
cout << s << " ";
return level;
}
// This function mainly does BFS and prints the
// shortest path from src to dest. It is assumed
// that weight of every edge is 1
int Graph::findShortestPath(int src, int dest)
{
// Mark all the vertices as not visited
bool *visited = new bool[2*V];
int *parent = new int[2*V];
// Initialize parent[] and visited[]
for (int i = 0; i < 2*V; i++)
{
visited[i] = false;
parent[i] = -1;
}
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[src] = true;
queue.push_back(src);
// 'i' will be used to get all adjacent vertices of a vertex
list<int>::iterator i;
while (!queue.empty())
{
// Dequeue a vertex from queue and print it
int s = queue.front();
if (s == dest)
return printShortestPath(parent, s, dest);
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
parent[*i] = s;
}
}
}
}
// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
int V = 4;
Graph g(V);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 1);
g.addEdge(2, 0, 1);
g.addEdge(2, 3, 2);
g.addEdge(3, 3, 2);
int src = 0, dest = 3;
cout << "\nShortest Distance between " << src
<< " and " << dest << " is "
<< g.findShortestPath(src, dest);
return 0;
}
Java
// Java to shortest path from a given source vertex 's' to
// a given destination vertex 't'. Expected time complexity
// is O(V+E).
import java.util.*;
class GFG
{
// This class represents a directed graph using adjacency
// list representation
static class Graph
{
int V; // No. of vertices
Vector<Integer>[] adj; // No. of vertices
static int level;
// Constructor
@SuppressWarnings("unchecked")
Graph(int V)
{
this.V = V;
this.adj = new Vector[2 * V];
for (int i = 0; i < 2 * V; i++)
this.adj[i] = new Vector<>();
}
// adds an edge
public void addEdge(int v, int w, int weight)
{
// split all edges of weight 2 into two
// edges of weight 1 each. The intermediate
// vertex number is maximum vertex number + 1,
// that is V.
if (weight == 2)
{
adj[v].add(v + this.V);
adj[v + this.V].add(w);
} else // Weight is 1
adj[v].add(w); // Add w to v's list.
}
// print shortest path from a source vertex 's' to
// destination vertex 'd'.
public int printShortestPath(int[] parent, int s, int d)
{
level = 0;
// If we reached root of shortest path tree
if (parent[s] == -1)
{
System.out.printf("Shortest Path between"+
"%d and %d is %s ", s, d, s);
return level;
}
printShortestPath(parent, parent[s], d);
level++;
if (s < this.V)
System.out.printf("%d ", s);
return level;
}
// finds shortest path from source vertex 's' to
// destination vertex 'd'.
// This function mainly does BFS and prints the
// shortest path from src to dest. It is assumed
// that weight of every edge is 1
public int findShortestPath(int src, int dest)
{
boolean[] visited = new boolean[2 * this.V];
int[] parent = new int[2 * this.V];
// Initialize parent[] and visited[]
for (int i = 0; i < 2 * this.V; i++)
{
visited[i] = false;
parent[i] = -1;
}
// Create a queue for BFS
Queue<Integer> queue = new LinkedList<>();
// Mark the current node as visited and enqueue it
visited[src] = true;
queue.add(src);
while (!queue.isEmpty())
{
// Dequeue a vertex from queue and print it
int s = queue.peek();
if (s == dest)
return printShortestPath(parent, s, dest);
queue.poll();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
for (int i : this.adj[s])
{
if (!visited[i])
{
visited[i] = true;
queue.add(i);
parent[i] = s;
}
}
}
return 0;
}
}
// Driver Code
public static void main(String[] args)
{
// Create a graph given in the above diagram
int V = 4;
Graph g = new Graph(V);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 1);
g.addEdge(2, 0, 1);
g.addEdge(2, 3, 2);
g.addEdge(3, 3, 2);
int src = 0, dest = 3;
System.out.printf("\nShortest Distance between" +
" %d and %d is %d\n", src,
dest, g.findShortestPath(src, dest));
}
}
// This code is contributed by
// sanjeev2552
Python
''' Program to shortest path from a given source vertex s to
a given destination vertex t. Expected time complexity
is O(V+E)'''
from collections import defaultdict
#This class represents a directed graph using adjacency list representation
class Graph:
def __init__(self,vertices):
self.V = vertices #No. of vertices
self.V_org = vertices
self.graph = defaultdict(list) # default dictionary to store graph
# function to add an edge to graph
def addEdge(self,u,v,w):
if w == 1:
self.graph[u].append(v)
else:
'''split all edges of weight 2 into two
edges of weight 1 each. The intermediate
vertex number is maximum vertex number + 1,
that is V.'''
self.graph[u].append(self.V)
self.graph[self.V].append(v)
self.V = self.V + 1
# To print the shortest path stored in parent[]
def printPath(self, parent, j):
Path_len = 1
if parent[j] == -1 and j < self.V_org : #Base Case : If j is source
print j,
return 0 # when parent[-1] then path length = 0
l = self.printPath(parent , parent[j])
#increment path length
Path_len = l + Path_len
# print node only if its less than original node length.
# i.e do not print any new node that has been added later
if j < self.V_org :
print j,
return Path_len
''' This function mainly does BFS and prints the
shortest path from src to dest. It is assumed
that weight of every edge is 1'''
def findShortestPath(self,src, dest):
# Mark all the vertices as not visited
# Initialize parent[] and visited[]
visited =[False]*(self.V)
parent =[-1]*(self.V)
# Create a queue for BFS
queue=[]
# Mark the source node as visited and enqueue it
queue.append(src)
visited[src] = True
while queue :
# Dequeue a vertex from queue
s = queue.pop(0)
# if s = dest then print the path and return
if s == dest:
return self.printPath(parent, s)
# Get all adjacent vertices of the dequeued vertex s
# If a adjacent has not been visited, then mark it
# visited and enqueue it
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
parent[i] = s
# Create a graph given in the above diagram
g = Graph(4)
g.addEdge(0, 1, 2)
g.addEdge(0, 2, 2)
g.addEdge(1, 2, 1)
g.addEdge(1, 3, 1)
g.addEdge(2, 0, 1)
g.addEdge(2, 3, 2)
g.addEdge(3, 3, 2)
src = 0; dest = 3
print ("Shortest Path between %d and %d is " %(src, dest)),
l = g.findShortestPath(src, dest)
print ("\nShortest Distance between %d and %d is %d " %(src, dest, l)),
#This code is contributed by Neelam Yadav
C#
// C# to shortest path from a given source vertex 's' to
// a given destination vertex 't'. Expected time complexity
// is O(V+E).
using System;
using System.Collections.Generic;
class GFG
{
// This class represents a directed graph using adjacency
// list representation
class Graph
{
public int V; // No. of vertices
public List<int>[] adj; // No. of vertices
static int level;
// Constructor
public Graph(int V)
{
this.V = V;
this.adj = new List<int>[2 * V];
for (int i = 0; i < 2 * V; i++)
this.adj[i] = new List<int>();
}
// adds an edge
public void addEdge(int v, int w, int weight)
{
// split all edges of weight 2 into two
// edges of weight 1 each. The intermediate
// vertex number is maximum vertex number + 1,
// that is V.
if (weight == 2)
{
adj[v].Add(v + this.V);
adj[v + this.V].Add(w);
} else // Weight is 1
adj[v].Add(w); // Add w to v's list.
}
// print shortest path from a source vertex 's' to
// destination vertex 'd'.
public int printShortestPath(int[] parent, int s, int d)
{
level = 0;
// If we reached root of shortest path tree
if (parent[s] == -1)
{
Console.Write("Shortest Path between"+
"{0} and {1} is {2} ", s, d, s);
return level;
}
printShortestPath(parent, parent[s], d);
level++;
if (s < this.V)
Console.Write("{0} ", s);
return level;
}
// finds shortest path from source vertex 's' to
// destination vertex 'd'.
// This function mainly does BFS and prints the
// shortest path from src to dest. It is assumed
// that weight of every edge is 1
public int findShortestPath(int src, int dest)
{
bool[] visited = new bool[2 * this.V];
int[] parent = new int[2 * this.V];
// Initialize parent[] and visited[]
for (int i = 0; i < 2 * this.V; i++)
{
visited[i] = false;
parent[i] = -1;
}
// Create a queue for BFS
List<int> queue = new List<int>();
// Mark the current node as visited and enqueue it
visited[src] = true;
queue.Add(src);
while (queue.Count != 0)
{
// Dequeue a vertex from queue and print it
int s = queue[0];
if (s == dest)
return printShortestPath(parent, s, dest);
queue.RemoveAt(0);
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
foreach (int i in this.adj[s])
{
if (!visited[i])
{
visited[i] = true;
queue.Add(i);
parent[i] = s;
}
}
}
return 0;
}
}
// Driver Code
public static void Main(String[] args)
{
// Create a graph given in the above diagram
int V = 4;
Graph g = new Graph(V);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 1);
g.addEdge(2, 0, 1);
g.addEdge(2, 3, 2);
g.addEdge(3, 3, 2);
int src = 0, dest = 3;
Console.Write("\nShortest Distance between" +
" {0} and {1} is {2}\n", src,
dest, g.findShortestPath(src, dest));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find shortest path
// from a given source vertex 's' to
// a given destination vertex 't'. Expected time complexity
// is O(V+E).
// This class represents a directed graph using adjacency
// list representation
class Graph
{
constructor(V)
{
this.V = V;
this.adj = new Array(2 * V);
this.level = 0;
for (let i = 0; i < 2 * V; i++)
this.adj[i] = [];
}
// adds an edge
addEdge(v, w, weight)
{
// split all edges of weight 2 into two
// edges of weight 1 each. The intermediate
// vertex number is maximum vertex number + 1,
// that is V.
if (weight == 2)
{
this.adj[v].push(v + this.V);
this.adj[v + this.V].push(w);
} else // Weight is 1
this.adj[v].push(w); // Add w to v's list.
}
// print shortest path from a source vertex 's' to
// destination vertex 'd'.
printShortestPath(parent, s, d)
{
this.level = 0;
// If we reached root of shortest path tree
if (parent[s] == -1)
{
document.write("Shortest Path between " + s + " and " + d + " is " + s + " ");
return this.level;
}
this.printShortestPath(parent, parent[s], d);
this.level++;
if (s < this.V)
document.write(s + " ");
return this.level;
}
// finds shortest path from source vertex 's' to
// destination vertex 'd'.
// This function mainly does BFS and prints the
// shortest path from src to dest. It is assumed
// that weight of every edge is 1
findShortestPath(src, dest)
{
let visited = new Array(2 * this.V);
let parent = new Array(2 * this.V);
// Initialize parent[] and visited[]
for (let i = 0; i < 2 * this.V; i++)
{
visited[i] = false;
parent[i] = -1;
}
// Create a queue for BFS
let queue = [];
// Mark the current node as visited and enqueue it
visited[src] = true;
queue.push(src);
while (queue.length > 0)
{
// Dequeue a vertex from queue and print it
let s = queue[0];
if (s == dest)
return this.printShortestPath(parent, s, dest);
queue.shift();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
this.adj[s].forEach(i => {
if (!visited[i]){
visited[i] = true;
queue.push(i);
parent[i] = s;
}
});
}
return 0;
}
}
// Driver Code
// Create a graph given in the above diagram
let V = 4;
let g = new Graph(V);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 1);
g.addEdge(2, 0, 1);
g.addEdge(2, 3, 2);
g.addEdge(3, 3, 2);
let src = 0, dest = 3;
document.write("<br />Shortest Distance between " + src + " and " + dest + " is " +
g.findShortestPath(src, dest));
// This code is contributed by cavi4762
</script>
Producción
Shortest Path between 0 and 3 is 0 1 3 Shortest Distance between 0 and 3 is 3
¿Cómo es este enfoque O(V+E)? En el peor de los casos, todos los bordes tienen un peso de 2 y necesitamos hacer operaciones O(E) para dividir todos los bordes y los vértices de 2V, por lo que la complejidad del tiempo se convierte en O(E) + O(V+E), que es O(V+). MI). Este artículo es una contribución de Aditya Goel .
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