Dado un gráfico y dos Nodes uyv , la tarea es imprimir el camino más corto entre uyv usando el algoritmo de Floyd Warshall .
Ejemplos:
Entrada: u = 1, v = 3
Salida: 1 -> 2 -> 3
Explicación:
El camino más corto de 1 a 3 es a través del vértice 2 con costo total 3.
El primer borde es 1 -> 2 con costo 2 y el segundo borde es 2 -> 3 con costo 1.Entrada: u = 0, v = 2
Salida: 0 -> 1 -> 2
Explicación:
El camino más corto de 0 a 2 es a través del vértice 1 con costo total = 5
Acercarse:
- La idea principal aquí es usar una array (arreglo 2D) que hará un seguimiento del siguiente Node para señalar si la ruta más corta cambia para cualquier par de Nodes. Inicialmente, el camino más corto entre dos Nodes u y v es v (es decir, el borde directo desde u -> v).
- Inicializando la siguiente array
Si la ruta existe entre dos Nodes, entonces Siguiente[u][v] = v
, de lo contrario establecemos Siguiente[u][v] = -1
- Modificación en el algoritmo de Floyd Warshall
Dentro de la condición if del algoritmo de Floyd Warshall agregaremos una declaración Next[i][j] = Next[i][k]
(eso significa que encontramos el camino más corto entre i, j a través de un Node intermedio k).
- Así es como se vería nuestra condición if
if(dis[i][j] > dis[i][k] + dis[k][j])
{
dis[i][j] = dis[i][k] + dis[k][j];
Next[i][j] = Next[i][k];
}
- Para construir una ruta usando estos Nodes, simplemente comenzaremos a recorrer el Node u mientras actualizamos su valor a next[u][v] hasta llegar al Node v .
path = [u]
while u != v:
u = Next[u][v]
path.append(u)
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the shortest
// path between any two nodes using
// Floyd Warshall Algorithm.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100
// Infinite value for array
const int INF = 1e7;
int dis[MAXN][MAXN];
int Next[MAXN][MAXN];
// Initializing the distance and
// Next array
void initialise(int V,
vector<vector<int> >& graph)
{
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dis[i][j] = graph[i][j];
// No edge between node
// i and j
if (graph[i][j] == INF)
Next[i][j] = -1;
else
Next[i][j] = j;
}
}
}
// Function construct the shortest
// path between u and v
vector<int> constructPath(int u,
int v)
{
// If there's no path between
// node u and v, simply return
// an empty array
if (Next[u][v] == -1)
return {};
// Storing the path in a vector
vector<int> path = { u };
while (u != v) {
u = Next[u][v];
path.push_back(u);
}
return path;
}
// Standard Floyd Warshall Algorithm
// with little modification Now if we find
// that dis[i][j] > dis[i][k] + dis[k][j]
// then we modify next[i][j] = next[i][k]
void floydWarshall(int V)
{
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// We cannot travel through
// edge that doesn't exist
if (dis[i][k] == INF
|| dis[k][j] == INF)
continue;
if (dis[i][j] > dis[i][k]
+ dis[k][j]) {
dis[i][j] = dis[i][k]
+ dis[k][j];
Next[i][j] = Next[i][k];
}
}
}
}
}
// Print the shortest path
void printPath(vector<int>& path)
{
int n = path.size();
for (int i = 0; i < n - 1; i++)
cout << path[i] << " -> ";
cout << path[n - 1] << endl;
}
// Driver code
int main()
{
int V = 4;
vector<vector<int> > graph
= { { 0, 3, INF, 7 },
{ 8, 0, 2, INF },
{ 5, INF, 0, 1 },
{ 2, INF, INF, 0 } };
// Function to initialise the
// distance and Next array
initialise(V, graph);
// Calling Floyd Warshall Algorithm,
// this will update the shortest
// distance as well as Next array
floydWarshall(V);
vector<int> path;
// Path from node 1 to 3
cout << "Shortest path from 1 to 3: ";
path = constructPath(1, 3);
printPath(path);
// Path from node 0 to 2
cout << "Shortest path from 0 to 2: ";
path = constructPath(0, 2);
printPath(path);
// path from node 3 to 2
cout << "Shortest path from 3 to 2: ";
path = constructPath(3, 2);
printPath(path);
return 0;
}
Java
// Java program to find the shortest
// path between any two nodes using
// Floyd Warshall Algorithm.
import java.util.*;
class GFG{
static final int MAXN = 100;
// Infinite value for array
static int INF = (int) 1e7;
static int [][]dis = new int[MAXN][MAXN];
static int [][]Next = new int[MAXN][MAXN];
// Initializing the distance and
// Next array
static void initialise(int V,
int [][] graph)
{
for(int i = 0; i < V; i++)
{
for(int j = 0; j < V; j++)
{
dis[i][j] = graph[i][j];
// No edge between node
// i and j
if (graph[i][j] == INF)
Next[i][j] = -1;
else
Next[i][j] = j;
}
}
}
// Function construct the shortest
// path between u and v
static Vector<Integer> constructPath(int u,
int v)
{
// If there's no path between
// node u and v, simply return
// an empty array
if (Next[u][v] == -1)
return null;
// Storing the path in a vector
Vector<Integer> path = new Vector<Integer>();
path.add(u);
while (u != v)
{
u = Next[u][v];
path.add(u);
}
return path;
}
// Standard Floyd Warshall Algorithm
// with little modification Now if we find
// that dis[i][j] > dis[i][k] + dis[k][j]
// then we modify next[i][j] = next[i][k]
static void floydWarshall(int V)
{
for(int k = 0; k < V; k++)
{
for(int i = 0; i < V; i++)
{
for(int j = 0; j < V; j++)
{
// We cannot travel through
// edge that doesn't exist
if (dis[i][k] == INF ||
dis[k][j] == INF)
continue;
if (dis[i][j] > dis[i][k] +
dis[k][j])
{
dis[i][j] = dis[i][k] +
dis[k][j];
Next[i][j] = Next[i][k];
}
}
}
}
}
// Print the shortest path
static void printPath(Vector<Integer> path)
{
int n = path.size();
for(int i = 0; i < n - 1; i++)
System.out.print(path.get(i) + " -> ");
System.out.print(path.get(n - 1) + "\n");
}
// Driver code
public static void main(String[] args)
{
int V = 4;
int [][] graph = { { 0, 3, INF, 7 },
{ 8, 0, 2, INF },
{ 5, INF, 0, 1 },
{ 2, INF, INF, 0 } };
// Function to initialise the
// distance and Next array
initialise(V, graph);
// Calling Floyd Warshall Algorithm,
// this will update the shortest
// distance as well as Next array
floydWarshall(V);
Vector<Integer> path;
// Path from node 1 to 3
System.out.print("Shortest path from 1 to 3: ");
path = constructPath(1, 3);
printPath(path);
// Path from node 0 to 2
System.out.print("Shortest path from 0 to 2: ");
path = constructPath(0, 2);
printPath(path);
// Path from node 3 to 2
System.out.print("Shortest path from 3 to 2: ");
path = constructPath(3, 2);
printPath(path);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to find the shortest
# path between any two nodes using
# Floyd Warshall Algorithm.
# Initializing the distance and
# Next array
def initialise(V):
global dis, Next
for i in range(V):
for j in range(V):
dis[i][j] = graph[i][j]
# No edge between node
# i and j
if (graph[i][j] == INF):
Next[i][j] = -1
else:
Next[i][j] = j
# Function construct the shortest
# path between u and v
def constructPath(u, v):
global graph, Next
# If there's no path between
# node u and v, simply return
# an empty array
if (Next[u][v] == -1):
return {}
# Storing the path in a vector
path = [u]
while (u != v):
u = Next[u][v]
path.append(u)
return path
# Standard Floyd Warshall Algorithm
# with little modification Now if we find
# that dis[i][j] > dis[i][k] + dis[k][j]
# then we modify next[i][j] = next[i][k]
def floydWarshall(V):
global dist, Next
for k in range(V):
for i in range(V):
for j in range(V):
# We cannot travel through
# edge that doesn't exist
if (dis[i][k] == INF or dis[k][j] == INF):
continue
if (dis[i][j] > dis[i][k] + dis[k][j]):
dis[i][j] = dis[i][k] + dis[k][j]
Next[i][j] = Next[i][k]
# Print the shortest path
def printPath(path):
n = len(path)
for i in range(n - 1):
print(path[i], end=" -> ")
print (path[n - 1])
# Driver code
if __name__ == '__main__':
MAXM,INF = 100,10**7
dis = [[-1 for i in range(MAXM)] for i in range(MAXM)]
Next = [[-1 for i in range(MAXM)] for i in range(MAXM)]
V = 4
graph = [ [ 0, 3, INF, 7 ],
[ 8, 0, 2, INF ],
[ 5, INF, 0, 1 ],
[ 2, INF, INF, 0 ] ]
# Function to initialise the
# distance and Next array
initialise(V)
# Calling Floyd Warshall Algorithm,
# this will update the shortest
# distance as well as Next array
floydWarshall(V)
path = []
# Path from node 1 to 3
print("Shortest path from 1 to 3: ", end = "")
path = constructPath(1, 3)
printPath(path)
# Path from node 0 to 2
print("Shortest path from 0 to 2: ", end = "")
path = constructPath(0, 2)
printPath(path)
# Path from node 3 to 2
print("Shortest path from 3 to 2: ", end = "")
path = constructPath(3, 2)
printPath(path)
# This code is contributed by mohit kumar 29
C#
// C# program to find the shortest
// path between any two nodes using
// Floyd Warshall Algorithm.
using System;
using System.Collections.Generic;
class GFG{
static readonly int MAXN = 100;
// Infinite value for array
static int INF = (int)1e7;
static int [,]dis = new int[MAXN, MAXN];
static int [,]Next = new int[MAXN, MAXN];
// Initializing the distance and
// Next array
static void initialise(int V,
int [,] graph)
{
for(int i = 0; i < V; i++)
{
for(int j = 0; j < V; j++)
{
dis[i, j] = graph[i, j];
// No edge between node
// i and j
if (graph[i, j] == INF)
Next[i, j] = -1;
else
Next[i, j] = j;
}
}
}
// Function construct the shortest
// path between u and v
static List<int> constructPath(int u, int v)
{
// If there's no path between
// node u and v, simply return
// an empty array
if (Next[u, v] == -1)
return null;
// Storing the path in a vector
List<int> path = new List<int>();
path.Add(u);
while (u != v)
{
u = Next[u, v];
path.Add(u);
}
return path;
}
// Standard Floyd Warshall Algorithm
// with little modification Now if we find
// that dis[i,j] > dis[i,k] + dis[k,j]
// then we modify next[i,j] = next[i,k]
static void floydWarshall(int V)
{
for(int k = 0; k < V; k++)
{
for(int i = 0; i < V; i++)
{
for(int j = 0; j < V; j++)
{
// We cannot travel through
// edge that doesn't exist
if (dis[i, k] == INF ||
dis[k, j] == INF)
continue;
if (dis[i, j] > dis[i, k] +
dis[k, j])
{
dis[i, j] = dis[i, k] +
dis[k, j];
Next[i, j] = Next[i, k];
}
}
}
}
}
// Print the shortest path
static void printPath(List<int> path)
{
int n = path.Count;
for(int i = 0; i < n - 1; i++)
Console.Write(path[i] + " -> ");
Console.Write(path[n - 1] + "\n");
}
// Driver code
public static void Main(String[] args)
{
int V = 4;
int [,] graph = { { 0, 3, INF, 7 },
{ 8, 0, 2, INF },
{ 5, INF, 0, 1 },
{ 2, INF, INF, 0 } };
// Function to initialise the
// distance and Next array
initialise(V, graph);
// Calling Floyd Warshall Algorithm,
// this will update the shortest
// distance as well as Next array
floydWarshall(V);
List<int> path;
// Path from node 1 to 3
Console.Write("Shortest path from 1 to 3: ");
path = constructPath(1, 3);
printPath(path);
// Path from node 0 to 2
Console.Write("Shortest path from 0 to 2: ");
path = constructPath(0, 2);
printPath(path);
// Path from node 3 to 2
Console.Write("Shortest path from 3 to 2: ");
path = constructPath(3, 2);
printPath(path);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to find the shortest
// path between any two nodes using
// Floyd Warshall Algorithm.
let MAXN = 100;
// Infinite value for array
let INF = 1e7;
let dis = new Array(MAXN);
let Next = new Array(MAXN);
for(let i = 0; i < MAXN; i++)
{
dis[i] = new Array(MAXN);
Next[i] = new Array(MAXN);
}
// Initializing the distance and
// Next array
function initialise(V, graph)
{
for(let i = 0; i < V; i++)
{
for(let j = 0; j < V; j++)
{
dis[i][j] = graph[i][j];
// No edge between node
// i and j
if (graph[i][j] == INF)
Next[i][j] = -1;
else
Next[i][j] = j;
}
}
}
// Function construct the shortest
// path between u and v
function constructPath(u, v)
{
// If there's no path between
// node u and v, simply return
// an empty array
if (Next[u][v] == -1)
return null;
// Storing the path in a vector
let path = [];
path.push(u);
while (u != v)
{
u = Next[u][v];
path.push(u);
}
return path;
}
// Standard Floyd Warshall Algorithm
// with little modification Now if we find
// that dis[i][j] > dis[i][k] + dis[k][j]
// then we modify next[i][j] = next[i][k]
function floydWarshall(V)
{
for(let k = 0; k < V; k++)
{
for(let i = 0; i < V; i++)
{
for(let j = 0; j < V; j++)
{
// We cannot travel through
// edge that doesn't exist
if (dis[i][k] == INF ||
dis[k][j] == INF)
continue;
if (dis[i][j] > dis[i][k] +
dis[k][j])
{
dis[i][j] = dis[i][k] +
dis[k][j];
Next[i][j] = Next[i][k];
}
}
}
}
}
// Print the shortest path
function printPath(path)
{
let n = path.length;
for(let i = 0; i < n - 1; i++)
document.write(path[i] + " -> ");
document.write(path[n - 1] + "<br>");
}
// Driver code
let V = 4;
let graph = [ [ 0, 3, INF, 7 ],
[ 8, 0, 2, INF ],
[ 5, INF, 0, 1 ],
[ 2, INF, INF, 0 ] ];
// Function to initialise the
// distance and Next array
initialise(V, graph);
// Calling Floyd Warshall Algorithm,
// this will update the shortest
// distance as well as Next array
floydWarshall(V);
let path;
// Path from node 1 to 3
document.write("Shortest path from 1 to 3: ");
path = constructPath(1, 3);
printPath(path);
// Path from node 0 to 2
document.write("Shortest path from 0 to 2: ");
path = constructPath(0, 2);
printPath(path);
// Path from node 3 to 2
document.write("Shortest path from 3 to 2: ");
path = constructPath(3, 2);
printPath(path);
// This code is contributed by unknown2108
</script>
Producción:
Shortest path from 1 to 3: 1 -> 2 -> 3 Shortest path from 0 to 2: 0 -> 1 -> 2 Shortest path from 3 to 2: 3 -> 0 -> 1 -> 2
Análisis de Complejidad:
- La complejidad temporal del algoritmo de Floyd Warshall es O(V 3 )
- Para encontrar la ruta más corta, la complejidad del tiempo es O (V) por consulta.
Nota: sería eficiente utilizar el algoritmo de Floyd Warshall cuando su gráfico contenga un par de cientos de vértices y necesite responder varias consultas relacionadas con la ruta más corta.
Publicación traducida automáticamente
Artículo escrito por AyushGupta31 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA