Hemos presentado a Bellman Ford y discutido sobre la implementación aquí .
Entrada: gráfico y un vértice de origen src
Salida: distancia más corta a todos los vértices desde src . Si hay un ciclo de peso negativo, no se calculan las distancias más cortas, se informa un ciclo de peso negativo.
1) Este paso inicializa las distancias desde la fuente a todos los vértices como infinitas y la distancia a la fuente misma como 0. Cree una array dist[] de tamaño |V| con todos los valores infinitos excepto dist[src] donde src es el vértice de origen.
2) Este paso calcula las distancias más cortas. Haz lo siguiente |V|-1 veces donde |V| es el número de vértices en el gráfico dado.
….. a)Haga lo siguiente para cada arista uv
………………Si dist[v] > dist[u] + peso de arista uv, entonces actualice dist[v]
………………….dist[v] = dist[u ] + peso del borde uv
3) Este paso informa si hay un ciclo de peso negativo en el gráfico. Haga lo siguiente para cada borde uv
…… Si dist[v] > dist[u] + peso del borde uv, entonces «El gráfico contiene un ciclo de peso negativo»
La idea del paso 3 es que el paso 2 garantiza las distancias más cortas si el gráfico no contiene Ciclo de peso negativo. Si iteramos a través de todos los bordes una vez más y obtenemos una ruta más corta para cualquier vértice, entonces hay un ciclo de peso negativo .
Ejemplo
Entendamos el algoritmo con el siguiente gráfico de ejemplo. Las imágenes están tomadas de esta fuente.
Sea 0 el vértice fuente dado. Inicialice todas las distancias como infinitas, excepto la distancia a la fuente misma. El número total de vértices en el gráfico es 5, por lo que todos los bordes deben procesarse 4 veces.
Deje que todos los bordes se procesen en el siguiente orden: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C) , (E,D). Obtenemos distancias de seguimiento cuando todos los bordes se procesan por primera vez. La primera fila muestra las distancias iniciales. La segunda fila muestra las distancias cuando se procesan los bordes (B, E), (D, B), (B, D) y (A, B). La tercera fila muestra las distancias cuando se procesa (A, C). La cuarta fila muestra cuándo se procesan (D, C), (B, C) y (E, D).
La primera iteración garantiza dar todos los caminos más cortos que tienen como máximo 1 borde de largo. Obtenemos las siguientes distancias cuando todos los bordes se procesan por segunda vez (la última fila muestra los valores finales).
La segunda iteración garantiza dar todos los caminos más cortos que tienen como máximo 2 aristas de largo. El algoritmo procesa todos los bordes 2 veces más. Las distancias se minimizan después de la segunda iteración, por lo que las iteraciones tercera y cuarta no actualizan las distancias.
C++
// A C++ program for Bellman-Ford's single source
// shortest path algorithm.
#include <bits/stdc++.h>
using namespace std;
// The main function that finds shortest
// distances from src to all other vertices
// using Bellman-Ford algorithm. The function
// also detects negative weight cycle
// The row graph[i] represents i-th edge with
// three values u, v and w.
void BellmanFord(int graph[][3], int V, int E,
int src)
{
// Initialize distance of all vertices as infinite.
int dis[V];
for (int i = 0; i < V; i++)
dis[i] = INT_MAX;
// initialize distance of source as 0
dis[src] = 0;
// Relax all edges |V| - 1 times. A simple
// shortest path from src to any other
// vertex can have at-most |V| - 1 edges
for (int i = 0; i < V - 1; i++) {
for (int j = 0; j < E; j++) {
if (dis[graph[j][0]] != INT_MAX && dis[graph[j][0]] + graph[j][2] <
dis[graph[j][1]])
dis[graph[j][1]] =
dis[graph[j][0]] + graph[j][2];
}
}
// check for negative-weight cycles.
// The above step guarantees shortest
// distances if graph doesn't contain
// negative weight cycle. If we get a
// shorter path, then there is a cycle.
for (int i = 0; i < E; i++) {
int x = graph[i][0];
int y = graph[i][1];
int weight = graph[i][2];
if (dis[x] != INT_MAX &&
dis[x] + weight < dis[y])
cout << "Graph contains negative"
" weight cycle"
<< endl;
}
cout << "Vertex Distance from Source" << endl;
for (int i = 0; i < V; i++)
cout << i << "\t\t" << dis[i] << endl;
}
// Driver program to test above functions
int main()
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
// Every edge has three values (u, v, w) where
// the edge is from vertex u to v. And weight
// of the edge is w.
int graph[][3] = { { 0, 1, -1 }, { 0, 2, 4 },
{ 1, 2, 3 }, { 1, 3, 2 },
{ 1, 4, 2 }, { 3, 2, 5 },
{ 3, 1, 1 }, { 4, 3, -3 } };
BellmanFord(graph, V, E, 0);
return 0;
}
Java
// A Java program for Bellman-Ford's single source
// shortest path algorithm.
class GFG
{
// The main function that finds shortest
// distances from src to all other vertices
// using Bellman-Ford algorithm. The function
// also detects negative weight cycle
// The row graph[i] represents i-th edge with
// three values u, v and w.
static void BellmanFord(int graph[][], int V, int E,
int src)
{
// Initialize distance of all vertices as infinite.
int []dis = new int[V];
for (int i = 0; i < V; i++)
dis[i] = Integer.MAX_VALUE;
// initialize distance of source as 0
dis[src] = 0;
// Relax all edges |V| - 1 times. A simple
// shortest path from src to any other
// vertex can have at-most |V| - 1 edges
for (int i = 0; i < V - 1; i++)
{
for (int j = 0; j < E; j++)
{
if (dis[graph[j][0]] != Integer.MAX_VALUE && dis[graph[j][0]] + graph[j][2] <
dis[graph[j][1]])
dis[graph[j][1]] =
dis[graph[j][0]] + graph[j][2];
}
}
// check for negative-weight cycles.
// The above step guarantees shortest
// distances if graph doesn't contain
// negative weight cycle. If we get a
// shorter path, then there is a cycle.
for (int i = 0; i < E; i++)
{
int x = graph[i][0];
int y = graph[i][1];
int weight = graph[i][2];
if (dis[x] != Integer.MAX_VALUE &&
dis[x] + weight < dis[y])
System.out.println("Graph contains negative"
+" weight cycle");
}
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i + "\t\t" + dis[i]);
}
// Driver code
public static void main(String[] args)
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
// Every edge has three values (u, v, w) where
// the edge is from vertex u to v. And weight
// of the edge is w.
int graph[][] = { { 0, 1, -1 }, { 0, 2, 4 },
{ 1, 2, 3 }, { 1, 3, 2 },
{ 1, 4, 2 }, { 3, 2, 5 },
{ 3, 1, 1 }, { 4, 3, -3 } };
BellmanFord(graph, V, E, 0);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for Bellman-Ford's
# single source shortest path algorithm.
from sys import maxsize
# The main function that finds shortest
# distances from src to all other vertices
# using Bellman-Ford algorithm. The function
# also detects negative weight cycle
# The row graph[i] represents i-th edge with
# three values u, v and w.
def BellmanFord(graph, V, E, src):
# Initialize distance of all vertices as infinite.
dis = [maxsize] * V
# initialize distance of source as 0
dis[src] = 0
# Relax all edges |V| - 1 times. A simple
# shortest path from src to any other
# vertex can have at-most |V| - 1 edges
for i in range(V - 1):
for j in range(E):
if dis[graph[j][0]] + \
graph[j][2] < dis[graph[j][1]]:
dis[graph[j][1]] = dis[graph[j][0]] + \
graph[j][2]
# check for negative-weight cycles.
# The above step guarantees shortest
# distances if graph doesn't contain
# negative weight cycle. If we get a
# shorter path, then there is a cycle.
for i in range(E):
x = graph[i][0]
y = graph[i][1]
weight = graph[i][2]
if dis[x] != maxsize and dis[x] + \
weight < dis[y]:
print("Graph contains negative weight cycle")
print("Vertex Distance from Source")
for i in range(V):
print("%d\t\t%d" % (i, dis[i]))
# Driver Code
if __name__ == "__main__":
V = 5 # Number of vertices in graph
E = 8 # Number of edges in graph
# Every edge has three values (u, v, w) where
# the edge is from vertex u to v. And weight
# of the edge is w.
graph = [[0, 1, -1], [0, 2, 4], [1, 2, 3],
[1, 3, 2], [1, 4, 2], [3, 2, 5],
[3, 1, 1], [4, 3, -3]]
BellmanFord(graph, V, E, 0)
# This code is contributed by
# sanjeev2552
C#
// C# program for Bellman-Ford's single source
// shortest path algorithm.
using System;
class GFG
{
// The main function that finds shortest
// distances from src to all other vertices
// using Bellman-Ford algorithm. The function
// also detects negative weight cycle
// The row graph[i] represents i-th edge with
// three values u, v and w.
static void BellmanFord(int [,]graph, int V,
int E, int src)
{
// Initialize distance of all vertices as infinite.
int []dis = new int[V];
for (int i = 0; i < V; i++)
dis[i] = int.MaxValue;
// initialize distance of source as 0
dis[src] = 0;
// Relax all edges |V| - 1 times. A simple
// shortest path from src to any other
// vertex can have at-most |V| - 1 edges
for (int i = 0; i < V - 1; i++)
{
for (int j = 0; j < E; j++)
{
if (dis[graph[j, 0]] = int.MaxValue && dis[graph[j, 0]] + graph[j, 2] <
dis[graph[j, 1]])
dis[graph[j, 1]] =
dis[graph[j, 0]] + graph[j, 2];
}
}
// check for negative-weight cycles.
// The above step guarantees shortest
// distances if graph doesn't contain
// negative weight cycle. If we get a
// shorter path, then there is a cycle.
for (int i = 0; i < E; i++)
{
int x = graph[i, 0];
int y = graph[i, 1];
int weight = graph[i, 2];
if (dis[x] != int.MaxValue &&
dis[x] + weight < dis[y])
Console.WriteLine("Graph contains negative" +
" weight cycle");
}
Console.WriteLine("Vertex Distance from Source");
for (int i = 0; i < V; i++)
Console.WriteLine(i + "\t\t" + dis[i]);
}
// Driver code
public static void Main(String[] args)
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
// Every edge has three values (u, v, w) where
// the edge is from vertex u to v. And weight
// of the edge is w.
int [,]graph = {{ 0, 1, -1 }, { 0, 2, 4 },
{ 1, 2, 3 }, { 1, 3, 2 },
{ 1, 4, 2 }, { 3, 2, 5 },
{ 3, 1, 1 }, { 4, 3, -3 }};
BellmanFord(graph, V, E, 0);
}
}
// This code is contributed by Princi Singh
PHP
<?php
// A PHP program for Bellman-Ford's single
// source shortest path algorithm.
// The main function that finds shortest
// distances from src to all other vertices
// using Bellman-Ford algorithm. The function
// also detects negative weight cycle
// The row graph[i] represents i-th edge with
// three values u, v and w.
function BellmanFord($graph, $V, $E, $src)
{
// Initialize distance of all vertices as infinite.
$dis = array();
for ($i = 0; $i < $V; $i++)
$dis[$i] = PHP_INT_MAX;
// initialize distance of source as 0
$dis[$src] = 0;
// Relax all edges |V| - 1 times. A simple
// shortest path from src to any other
// vertex can have at-most |V| - 1 edges
for ($i = 0; $i < $V - 1; $i++)
{
for ($j = 0; $j < $E; $j++)
{
if ($dis[$graph[$j][0]] != PHP_INT_MAX && $dis[$graph[$j][0]] + $graph[$j][2] <
$dis[$graph[$j][1]])
$dis[$graph[$j][1]] = $dis[$graph[$j][0]] +
$graph[$j][2];
}
}
// check for negative-weight cycles.
// The above step guarantees shortest
// distances if graph doesn't contain
// negative weight cycle. If we get a
// shorter path, then there is a cycle.
for ($i = 0; $i < $E; $i++)
{
$x = $graph[$i][0];
$y = $graph[$i][1];
$weight = $graph[$i][2];
if ($dis[$x] != PHP_INT_MAX &&
$dis[$x] + $weight < $dis[$y])
echo "Graph contains negative weight cycle \n";
}
echo "Vertex Distance from Source \n";
for ($i = 0; $i < $V; $i++)
echo $i, "\t\t", $dis[$i], "\n";
}
// Driver Code
$V = 5; // Number of vertices in graph
$E = 8; // Number of edges in graph
// Every edge has three values (u, v, w) where
// the edge is from vertex u to v. And weight
// of the edge is w.
$graph = array( array( 0, 1, -1 ), array( 0, 2, 4 ),
array( 1, 2, 3 ), array( 1, 3, 2 ),
array( 1, 4, 2 ), array( 3, 2, 5),
array( 3, 1, 1), array( 4, 3, -3 ) );
BellmanFord($graph, $V, $E, 0);
// This code is contributed by AnkitRai01
?>
Javascript
<script>
// Javascript program for Bellman-Ford's single source
// shortest path algorithm.
// The main function that finds shortest
// distances from src to all other vertices
// using Bellman-Ford algorithm. The function
// also detects negative weight cycle
// The row graph[i] represents i-th edge with
// three values u, v and w.
function BellmanFord(graph, V, E, src)
{
// Initialize distance of all vertices as infinite.
var dis = Array(V).fill(1000000000);
// initialize distance of source as 0
dis[src] = 0;
// Relax all edges |V| - 1 times. A simple
// shortest path from src to any other
// vertex can have at-most |V| - 1 edges
for (var i = 0; i < V - 1; i++)
{
for (var j = 0; j < E; j++)
{
if ((dis[graph[j][0]] + graph[j][2]) < dis[graph[j][1]])
dis[graph[j][1]] = dis[graph[j][0]] + graph[j][2];
}
}
// check for negative-weight cycles.
// The above step guarantees shortest
// distances if graph doesn't contain
// negative weight cycle. If we get a
// shorter path, then there is a cycle.
for (var i = 0; i < E; i++)
{
var x = graph[i][0];
var y = graph[i][1];
var weight = graph[i][2];
if ((dis[x] != 1000000000) &&
(dis[x] + weight < dis[y]))
document.write("Graph contains negative" +
" weight cycle<br>");
}
document.write("Vertex Distance from Source<br>");
for (var i = 0; i < V; i++)
document.write(i + " " + dis[i] + "<br>");
}
// Driver code
var V = 5; // Number of vertices in graph
var E = 8; // Number of edges in graph
// Every edge has three values (u, v, w) where
// the edge is from vertex u to v. And weight
// of the edge is w.
var graph = [[ 0, 1, -1 ], [ 0, 2, 4 ],
[ 1, 2, 3 ], [ 1, 3, 2 ],
[ 1, 4, 2 ], [ 3, 2, 5 ],
[ 3, 1, 1 ], [ 4, 3, -3 ]];
BellmanFord(graph, V, E, 0);
// This code is contributed by importantly.
</script>
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1
Complejidad de tiempo: O(VE)
Esta implementación es sugerida por PrateekGupta10
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