Prerrequisitos: Algoritmo Bellman-Ford
Dado un grafo ponderado dirigido con V vértices, E aristas y un vértice fuente S . La tarea es encontrar el camino más corto desde el vértice de origen a todos los demás vértices en el gráfico dado.
Ejemplo:
Entrada: V = 5, S = 1, arr = {{1, 2, 1}, {2, 3, 7}, {2, 4, -2}, {1, 3, 8}, {1, 4 , 9}, {3, 4, 3}, {2, 5, 3}, {4, 5, -3}}
Salida:
1, 0
2, 1
3, 8
4, -1
5, -4
Explicación: Para la entrada dada, el camino más corto de 1 a 1 es 0, 1 a 2 es 1 y así sucesivamente.
Entrada: V = 5, S = 1, arr = {{1, 2, -1}, {1, 3, 4}, {2, 3, 3}, {2, 4, 2}, {2, 5 , 2}, {4, 3, 5}, {4, 2, 1}, {5, 4, 3}}
Salida:
1, 0
2, -1
3, 2
4, 1
5, 1
Enfoque: el algoritmo más rápido de la ruta más corta se basa en el algoritmo de Bellman-Ford , donde cada vértice se usa para relajar sus vértices adyacentes, pero en el algoritmo SPF, se mantiene una cola de vértices y se agrega un vértice a la cola solo si ese vértice está relajado. Este proceso se repite hasta que no se pueden relajar más vértices.
Se pueden realizar los siguientes pasos para calcular el resultado:
- Cree una array d[] para almacenar la distancia más corta de todos los vértices desde el vértice de origen. Inicialice esta array hasta el infinito, excepto para d[S] = 0, donde S es el vértice de origen.
- Cree una cola Q y empuje el vértice de origen inicial en ella.
- mientras Queue no está vacío, haga lo siguiente para cada borde (u, v) en el gráfico
- Si d[v] > d[u] + peso de la arista(u, v)
- d[v] = d[u] + peso de la arista(u, v)
- Si el vértice v no está presente en la cola, empuje el vértice v a la cola.
- mientras Queue no está vacío, haga lo siguiente para cada borde (u, v) en el gráfico
Nota: El término relajación significa actualizar el costo de todos los vértices conectados a un vértice v si esos costos mejorarían al incluir la ruta a través del vértice v . Esto se puede entender mejor a partir de una analogía entre la estimación del camino más corto y la longitud de un resorte de tensión helicoidal, que no está diseñado para compresión. Inicialmente, el costo del camino más corto es una sobreestimación, comparable a un resorte estirado. A medida que se encuentran caminos más cortos, el costo estimado se reduce y el resorte se relaja. Eventualmente, se encuentra el camino más corto, si existe, y el resorte se ha relajado hasta su longitud de reposo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of SPFA
#include <bits/stdc++.h>
using namespace std;
// Graph is stored as vector of vector of pairs
// first element of pair store vertex
// second element of pair store weight
vector<vector<pair<int, int> >> graph;
// Function to add edges in the graph
// connecting a pair of vertex(frm) and weight
// to another vertex(to) in graph
void addEdge(int frm, int to, int weight)
{
graph[frm].push_back({ to, weight });
}
// Function to print shortest distance from source
void print_distance(int d[], int V)
{
cout << "Vertex \t\t Distance"
<< " from source" << endl;
for (int i = 1; i <= V; i++) {
cout << i << " " << d[i] << '\n';
}
}
// Function to compute the SPF algorithm
void shortestPathFaster(int S, int V)
{
// Create array d to store shortest distance
int d[V + 1];
// Boolean array to check if vertex
// is present in queue or not
bool inQueue[V + 1] = { false };
// Initialize the distance from source to
// other vertex as INT_MAX(infinite)
for (int i = 0; i <= V; i++) {
d[i] = INT_MAX;
}
d[S] = 0;
queue<int> q;
q.push(S);
inQueue[S] = true;
while (!q.empty()) {
// Take the front vertex from Queue
int u = q.front();
q.pop();
inQueue[u] = false;
// Relaxing all the adjacent edges of
// vertex taken from the Queue
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i].first;
int weight = graph[u][i].second;
if (d[v] > d[u] + weight) {
d[v] = d[u] + weight;
// Check if vertex v is in Queue or not
// if not then push it into the Queue
if (!inQueue[v]) {
q.push(v);
inQueue[v] = true;
}
}
}
}
// Print the result
print_distance(d, V);
}
// Driver code
int main()
{
int V = 5;
int S = 1;
graph = vector<vector<pair<int,int>>> (V+1);
// Connect vertex a to b with weight w
// addEdge(a, b, w)
addEdge(1, 2, 1);
addEdge(2, 3, 7);
addEdge(2, 4, -2);
addEdge(1, 3, 8);
addEdge(1, 4, 9);
addEdge(3, 4, 3);
addEdge(2, 5, 3);
addEdge(4, 5, -3);
// Calling shortestPathFaster function
shortestPathFaster(S, V);
return 0;
}
Java
// Java implementation of SPFA
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Graph is stored as vector of vector of pairs
// first element of pair store vertex
// second element of pair store weight
static Vector<pair > []graph = new Vector[100000];
// Function to add edges in the graph
// connecting a pair of vertex(frm) and weight
// to another vertex(to) in graph
static void addEdge(int frm, int to, int weight)
{
graph[frm].add(new pair( to, weight ));
}
// Function to print shortest distance from source
static void print_distance(int d[], int V)
{
System.out.print("Vertex \t\t Distance"
+ " from source" +"\n");
for (int i = 1; i <= V; i++)
{
System.out.printf("%d \t\t %d\n", i, d[i]);
}
}
// Function to compute the SPF algorithm
static void shortestPathFaster(int S, int V)
{
// Create array d to store shortest distance
int []d = new int[V + 1];
// Boolean array to check if vertex
// is present in queue or not
boolean []inQueue = new boolean[V + 1];
// Initialize the distance from source to
// other vertex as Integer.MAX_VALUE(infinite)
for (int i = 0; i <= V; i++)
{
d[i] = Integer.MAX_VALUE;
}
d[S] = 0;
Queue<Integer> q = new LinkedList<>();
q.add(S);
inQueue[S] = true;
while (!q.isEmpty())
{
// Take the front vertex from Queue
int u = q.peek();
q.remove();
inQueue[u] = false;
// Relaxing all the adjacent edges of
// vertex taken from the Queue
for (int i = 0; i < graph[u].size(); i++)
{
int v = graph[u].get(i).first;
int weight = graph[u].get(i).second;
if (d[v] > d[u] + weight)
{
d[v] = d[u] + weight;
// Check if vertex v is in Queue or not
// if not then push it into the Queue
if (!inQueue[v])
{
q.add(v);
inQueue[v] = true;
}
}
}
}
// Print the result
print_distance(d, V);
}
// Driver code
public static void main(String[] args)
{
int V = 5;
int S = 1;
for (int i = 0; i < graph.length; i++)
{
graph[i] = new Vector<pair>();
}
// Connect vertex a to b with weight w
// addEdge(a, b, w)
addEdge(1, 2, 1);
addEdge(2, 3, 7);
addEdge(2, 4, -2);
addEdge(1, 3, 8);
addEdge(1, 4, 9);
addEdge(3, 4, 3);
addEdge(2, 5, 3);
addEdge(4, 5, -3);
// Calling shortestPathFaster function
shortestPathFaster(S, V);
}
}
// This code is contributed by 29AjayKumar
C#
// C# implementation of SPFA
using System;
using System.Collections.Generic;
class GFG
{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Graph is stored as vector of vector of pairs
// first element of pair store vertex
// second element of pair store weight
static List<pair> []graph = new List<pair>[100000];
// Function to add edges in the graph
// connecting a pair of vertex(frm) and weight
// to another vertex(to) in graph
static void addEdge(int frm, int to, int weight)
{
graph[frm].Add(new pair( to, weight ));
}
// Function to print shortest distance from source
static void print_distance(int []d, int V)
{
Console.Write("Vertex \t\t Distance"
+ " from source" +"\n");
for (int i = 1; i <= V; i++)
{
Console.Write("{0} \t\t {1}\n", i, d[i]);
}
}
// Function to compute the SPF algorithm
static void shortestPathFaster(int S, int V)
{
// Create array d to store shortest distance
int []d = new int[V + 1];
// Boolean array to check if vertex
// is present in queue or not
bool []inQueue = new bool[V + 1];
// Initialize the distance from source to
// other vertex as int.MaxValue(infinite)
for (int i = 0; i <= V; i++)
{
d[i] = int.MaxValue;
}
d[S] = 0;
Queue<int> q = new Queue<int>();
q.Enqueue(S);
inQueue[S] = true;
while (q.Count!=0)
{
// Take the front vertex from Queue
int u = q.Peek();
q.Dequeue();
inQueue[u] = false;
// Relaxing all the adjacent edges of
// vertex taken from the Queue
for (int i = 0; i < graph[u].Count; i++)
{
int v = graph[u][i].first;
int weight = graph[u][i].second;
if (d[v] > d[u] + weight)
{
d[v] = d[u] + weight;
// Check if vertex v is in Queue or not
// if not then push it into the Queue
if (!inQueue[v])
{
q.Enqueue(v);
inQueue[v] = true;
}
}
}
}
// Print the result
print_distance(d, V);
}
// Driver code
public static void Main(String[] args)
{
int V = 5;
int S = 1;
for (int i = 0; i < graph.Length; i++)
{
graph[i] = new List<pair>();
}
// Connect vertex a to b with weight w
// addEdge(a, b, w)
addEdge(1, 2, 1);
addEdge(2, 3, 7);
addEdge(2, 4, -2);
addEdge(1, 3, 8);
addEdge(1, 4, 9);
addEdge(3, 4, 3);
addEdge(2, 5, 3);
addEdge(4, 5, -3);
// Calling shortestPathFaster function
shortestPathFaster(S, V);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of SPFA
from collections import deque
# Graph is stored as vector of vector of pairs
# first element of pair store vertex
# second element of pair store weight
graph = [[] for _ in range(100000)]
# Function to add edges in the graph
# connecting a pair of vertex(frm) and weight
# to another vertex(to) in graph
def addEdge(frm, to, weight):
graph[frm].append([to, weight])
# Function to print shortest distance from source
def print_distance(d, V):
print("Vertex","\t","Distance from source")
for i in range(1, V + 1):
print(i,"\t",d[i])
# Function to compute the SPF algorithm
def shortestPathFaster(S, V):
# Create array d to store shortest distance
d = [10**9]*(V + 1)
# Boolean array to check if vertex
# is present in queue or not
inQueue = [False]*(V + 1)
d[S] = 0
q = deque()
q.append(S)
inQueue[S] = True
while (len(q) > 0):
# Take the front vertex from Queue
u = q.popleft()
inQueue[u] = False
# Relaxing all the adjacent edges of
# vertex taken from the Queue
for i in range(len(graph[u])):
v = graph[u][i][0]
weight = graph[u][i][1]
if (d[v] > d[u] + weight):
d[v] = d[u] + weight
# Check if vertex v is in Queue or not
# if not then append it into the Queue
if (inQueue[v] == False):
q.append(v)
inQueue[v] = True
# Print the result
print_distance(d, V)
# Driver code
if __name__ == '__main__':
V = 5
S = 1
# Connect vertex a to b with weight w
# addEdge(a, b, w)
addEdge(1, 2, 1)
addEdge(2, 3, 7)
addEdge(2, 4, -2)
addEdge(1, 3, 8)
addEdge(1, 4, 9)
addEdge(3, 4, 3)
addEdge(2, 5, 3)
addEdge(4, 5, -3)
# Calling shortestPathFaster function
shortestPathFaster(S, V)
# This code is contributed by mohit kumar 29
Javascript
<script>
// JavaScript implementation of SPFA
// Graph is stored as vector of vector of pairs
// first element of pair store vertex
// second element of pair store weight
let graph=new Array(100000);
// Function to add edges in the graph
// connecting a pair of vertex(frm) and weight
// to another vertex(to) in graph
function addEdge(frm,to,weight)
{
graph[frm].push([to, weight ]);
}
// Function to print shortest distance from source
function print_distance(d,V)
{
document.write(
"Vertex", " ", "Distance" + " from source" +"<br>"
);
for (let i = 1; i <= V; i++)
{
document.write( i+" "+
d[i]+"<br>");
}
}
// Function to compute the SPF algorithm
function shortestPathFaster(S,V)
{
// Create array d to store shortest distance
let d = new Array(V + 1);
// Boolean array to check if vertex
// is present in queue or not
let inQueue = new Array(V + 1);
// Initialize the distance from source to
// other vertex as Integer.MAX_VALUE(infinite)
for (let i = 0; i <= V; i++)
{
d[i] = Number.MAX_VALUE;
}
d[S] = 0;
let q = [];
q.push(S);
inQueue[S] = true;
while (q.length!=0)
{
// Take the front vertex from Queue
let u = q[0];
q.shift();
inQueue[u] = false;
// Relaxing all the adjacent edges of
// vertex taken from the Queue
for (let i = 0; i < graph[u].length; i++)
{
let v = graph[u][i][0];
let weight = graph[u][i][1];
if (d[v] > d[u] + weight)
{
d[v] = d[u] + weight;
// Check if vertex v is in Queue or not
// if not then push it into the Queue
if (!inQueue[v])
{
q.push(v);
inQueue[v] = true;
}
}
}
}
// Print the result
print_distance(d, V);
}
// Driver code
let V = 5;
let S = 1;
for (let i = 0; i < graph.length; i++)
{
graph[i] = [];
}
// Connect vertex a to b with weight w
// addEdge(a, b, w)
addEdge(1, 2, 1);
addEdge(2, 3, 7);
addEdge(2, 4, -2);
addEdge(1, 3, 8);
addEdge(1, 4, 9);
addEdge(3, 4, 3);
addEdge(2, 5, 3);
addEdge(4, 5, -3);
// Calling shortestPathFaster function
shortestPathFaster(S, V);
// This code is contributed by unknown2108
</script>
Producción:
Vertex Distance from source 1 0 2 1 3 8 4 -1 5 -4
Complejidad de tiempo: Complejidad de
tiempo promedio: O(|E|)
Complejidad de tiempo en el peor de los casos : O(|V|.|E|)
Nota: El límite en el tiempo de ejecución promedio aún no se ha probado.
Referencias: Algoritmo más rápido de la ruta más corta
Publicación traducida automáticamente
Artículo escrito por durgeshkumar30508 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA