Requisito previo: algoritmo de ruta más corta de Dijkstra Dado un gráfico
de array de adyacencia que representa rutas entre los Nodes en el gráfico dado. La tarea es encontrar el camino más corto con los bordes mínimos, es decir, si hay varios caminos cortos con el mismo costo, elija el que tenga el número mínimo de bordes. Considere el gráfico que se presenta a continuación:
Hay dos caminos desde el vértice 0 al vértice 3 con el peso de 12:
- 0 -> 1 -> 2 -> 3
- 0 -> 4 -> 3
Dado que el algoritmo de Dijkstra es un algoritmo codicioso que busca el vértice ponderado mínimo en cada iteración, el algoritmo original de Dijkstra generará la primera ruta, pero el resultado debería ser la segunda ruta, ya que contiene un número mínimo de aristas.
Ejemplos:
Entrada: gráfico[][] = { {0, 1, INFINITY, INFINITY, 10},
{1, 0, 4, INFINITY, INFINITY},
{INFINITY, 4, 0, 7, INFINITY},
{INFINITY, INFINITY, 7, 0, 2},
{10, INFINITO, INFINITO, 2, 0} };
Salida: 0->4->3
INFINITY aquí muestra que u y v no son vecinos
Entrada: graph[][] = { {0, 5, INFINITY, INFINITY},
{5, 0, 5, 10},
{INFINITY , 5, 0, 5},
{INFINITO, 10, 5, 0} };
Salida: 0->1->3
Enfoque: La idea del algoritmo es utilizar el algoritmo de Dijkstra original, pero también realizar un seguimiento de la longitud de los caminos mediante una array que almacena la longitud de los caminos desde el vértice de origen, por lo que si encontramos un camino más corto con el mismo peso, entonces lo tomaremos.
Sigamos el ejemplo superior iteración por iteración:
Consideremos que queremos encontrar el camino más corto desde el vértice 0 al vértice 3
Estado inicial: La distancia y el padre de todos los vértices son Infinito y NILL respectivamente, como de costumbre.
Pero ahora, tenemos una array más llamada pathlength[] que almacena la longitud de la ruta desde el vértice de origen hasta todos los vértices.
Inicialmente, configuramos todos los elementos delongitud de ruta[] a 0 .
Primera iteración: Primero buscamos el vértice que contiene la distancia mínima que es el vértice 0 , como se muestra en la imagen de arriba.
Luego, recorremos todos sus vecinos que no están ennegrecidos, que son 1 y 4 . Dado que la distancia de los vértices 1 y 4 es infinita, entonces reducimos sus pesos a 1 y 10 respectivamente. Actualice los padres y establezca la longitud de la ruta [] para cada vértice ( 1 y 4 ) en 1 porque se puede llegar a ellos desde el vértice de origen por 1 borde.
Después de eso, ennegrecemos el vértice como lo hace el algoritmo original de Dijkstra.
Segunda iteración: continuamos buscando el vértice no borrado que contiene la distancia mínima, que es el vértice 1 , y luego reducimos el peso de su vecino a 1 + 4 = 5 y actualizamos su padre como lo hace el algoritmo original de Dijkstra, y establecemos su pathlength[] a 2 , porque está a dos aristas del vértice de origen.
Finalmente, ennegrecemos el vértice 1 .
Tercera iteración: nuevamente, el vértice no ennegrecido que contiene la distancia mínima es el vértice 2 , por lo que actualizamos los vecinos no ennegrecidos. Tiene un vecino no ennegrecido que es el vértice 3 . Por lo tanto, actualizamos su peso de Infinito a 5 + 7 = 12 , luego establecemos su padre en 2 y establecemos su longitud de ruta [] en 3 porque tiene 3 aristas que se balancean desde el vértice de origen.
Finalmente, ennegrecemos el vértice 2 .
Cuarta iteración: en esta iteración, el algoritmo actúa de manera diferente al algoritmo original de Dijkstra. Buscamos el vértice no ennegrecido que contiene la distancia mínima que es 4 . Dado que la distancia al vértice 3 desde el vértice de origen es 12 (0->1->2->3) y la distancia del vértice 4 más la arista (4, 3) es 12 , significa que acabamos de encontrar un nuevo ruta al vértice 3 desde el vértice de origen con el mismo peso. Luego, verificamos si el nuevo camino es más corto (en bordes) que el existente y tomamos el que tiene los bordes mínimos.
Finalmente, ennegrecemos el vértice 4 .
Dado que los vértices V-1 están ennegrecidos, el algoritmo finaliza.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the shortest path
// with minimum edges in a graph
#include <iostream>
using namespace std;
#define INFINITY 9999
#define n 5
#define s 0
#define d 3
#define NILL -1
int MinDistance(int*, int*);
void PrintPath(int*, int);
// Function to find the shortest path
// with minimum edges in a graph
void Dijkstra(int Graph[n][n], int _n, int _s, int _d)
{
int i, u, v, count;
int dist[n];
int Blackened[n] = { 0 };
int pathlength[n] = { 0 };
int parent[n];
// The parent Of the source vertex is always equal to nill
parent[_s] = NILL;
// first, we initialize all distances to infinity.
for (i = 0; i < n; i++)
dist[i] = INFINITY;
dist[_s] = 0;
for (count = 0; count < n - 1; count++) {
u = MinDistance(dist, Blackened);
// if MinDistance() returns INFINITY, then the graph is not
// connected and we have traversed all of the vertices in the
// connected component of the source vertex, so it can reduce
// the time complexity sometimes
// In a directed graph, it means that the source vertex
// is not a root
if (u == INFINITY)
break;
else {
// Mark the vertex as Blackened
Blackened[u] = 1;
for (v = 0; v < n; v++) {
//distance to v via u should be smaller and the path length should be minimum
if (!Blackened[v] && Graph[u][v]
&& dist[u] + Graph[u][v] <= dist[v]
&& pathlength[u] + 1 < pathlength[v]) {
parent[v] = u;
pathlength[v] = pathlength[u] + 1;
}
}
}
}
// Printing the path
if (dist[_d] != INFINITY)
PrintPath(parent, _d);
else
cout << "There is no path between vertex "
<< _s << "to vertex " << _d;
}
int MinDistance(int* dist, int* Blackened)
{
int min = INFINITY, min_index, v;
for (v = 0; v < n; v++)
if (!Blackened[v] && dist[v] < min) {
min = dist[v];
min_index = v;
}
return min == INFINITY ? INFINITY : min_index;
}
// Function to print the path
void PrintPath(int* parent, int _d)
{
if (parent[_d] == NILL) {
cout << _d;
return;
}
PrintPath(parent, parent[_d]);
cout << "->" << _d;
}
// Driver code
int main()
{
// INFINITY means that u and v are not neighbors.
int Graph[n][n] = { { 0, 1, INFINITY, INFINITY, 10 },
{ 1, 0, 4, INFINITY, INFINITY },
{ INFINITY, 4, 0, 7, INFINITY },
{ INFINITY, INFINITY, 7, 0, 2 },
{ 10, INFINITY, INFINITY, 2, 0 } };
Dijkstra(Graph, n, s, d);
return 0;
}
Java
// Java program to find the shortest path
// with minimum edges in a graph
import java.io.*;
import java.util.*;
class GFG
{
static int INFINITY = 9999, n = 5, s = 0, d = 3, NILL = -1;
// Function to find the shortest path
// with minimum edges in a graph
static void Dijkstra(int[][] Graph, int _n, int _s, int _d)
{
int i, u, v, count;
int[] dist = new int[n];
int[] Blackened = new int[n];
int[] pathlength = new int[n];
int[] parent = new int[n];
// The parent Of the source vertex is always equal to nill
parent[_s] = NILL;
// first, we initialize all distances to infinity.
for (i = 0; i < n; i++)
dist[i] = INFINITY;
dist[_s] = 0;
for (count = 0; count < n - 1; count++)
{
u = MinDistance(dist, Blackened);
// if MinDistance() returns INFINITY, then the graph is not
// connected and we have traversed all of the vertices in the
// connected component of the source vertex, so it can reduce
// the time complexity sometimes
// In a directed graph, it means that the source vertex
// is not a root
if (u == INFINITY)
break;
else
{
// Mark the vertex as Blackened
Blackened[u] = 1;
for (v = 0; v < n; v++)
{
if (Blackened[v] == 0 && Graph[u][v] != 0
&& dist[u] + Graph[u][v] < dist[v])
{
parent[v] = u;
pathlength[v] = pathlength[parent[v]] + 1;
dist[v] = dist[u] + Graph[u][v];
}
else if (Blackened[v] == 0 && Graph[u][v] != 0
&& dist[u] + Graph[u][v] == dist[v]
&& pathlength[u] + 1 < pathlength[v])
{
parent[v] = u;
pathlength[v] = pathlength[u] + 1;
}
}
}
}
// Printing the path
if (dist[_d] != INFINITY)
PrintPath(parent, _d);
else
System.out.println("There is not path between vertex " +
_s + " to vertex " + _d);
}
static int MinDistance(int[] dist, int[] Blackened)
{
int min = INFINITY, min_index = -1, v;
for (v = 0; v < n; v++)
if (Blackened[v] == 0 && dist[v] < min)
{
min = dist[v];
min_index = v;
}
return min == INFINITY ? INFINITY : min_index;
}
// Function to print the path
static void PrintPath(int[] parent, int _d)
{
if (parent[_d] == NILL)
{
System.out.print(_d);
return;
}
PrintPath(parent, parent[_d]);
System.out.print("->" + _d);
}
// Driver Code
public static void main(String[] args)
{
// INFINITY means that u and v are not neighbors.
int[][] Graph = { { 0, 1, INFINITY, INFINITY, 10 },
{ 1, 0, 4, INFINITY, INFINITY },
{ INFINITY, 4, 0, 7, INFINITY },
{ INFINITY, INFINITY, 7, 0, 2 },
{ 10, INFINITY, INFINITY, 2, 0 } };
Dijkstra(Graph, n, s, d);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python program to find the shortest path
# with minimum edges in a graph
def Dijkstra(Graph, _s, _d):
row = len(Graph)
col = len(Graph[0])
dist = [float("Inf")] * row
Blackened =[0] * row
pathlength =[0] * row
parent = [-1] * row
dist[_s]= 0
for count in range(row-1):
u = MinDistance(dist, Blackened)
# if MinDistance() returns INFINITY, then the graph is not
# connected and we have traversed all of the vertices in the
# connected component of the source vertex, so it can reduce
# the time complexity sometimes
# In a directed graph, it means that the source vertex
# is not a root
if u == float("Inf"):
break
else:
# Mark the vertex as Blackened
Blackened[u]= 1
for v in range(row):
if Blackened[v]== 0 and Graph[u][v] and dist[u]+Graph[u][v]<dist[v]:
parent[v]= u
pathlength[v]= pathlength[parent[v]]+1
dist[v]= dist[u]+Graph[u][v]
elif Blackened[v]== 0 and Graph[u][v] and dist[u]+Graph[u][v]== dist[v] and pathlength[u]+1<pathlength[v]:
parent[v]= u
pathlength[v] = pathlength[u] + 1
if dist[_d]!= float("Inf"):
# Printing the path
PrintPath(parent, _d)
else:
print("There is no path between vertex ", _s, "to vertex ", _d)
# Function to print the path
def PrintPath(parent, _d):
if parent[_d]==-1:
print(_d,end='')
return
PrintPath(parent, parent[_d])
print("->", _d,end='')
def MinDistance(dist, Blackened):
min = float("Inf")
for v in range(len(dist)):
if not Blackened[v] and dist[v]<min:
min = dist[v]
Min_index = v
return float("Inf") if min == float("Inf") else Min_index
# Driver code
# float("Inf") means that u and v are not neighbors
Graph =[[0, 1, float("Inf"), float("Inf"), 10],
[1, 0, 4, float("Inf"), float("Inf")],
[float("Inf"), 4, 0, 7, float("Inf")],
[float("Inf"), float("Inf"), 7, 0, 2],
[10, float("Inf"), float("Inf"), 2, 0]]
Dijkstra(Graph, 0, 3)
C#
// C# program to find the shortest path
// with minimum edges in a graph
using System;
class GFG
{
static int INFINITY = 9999, n = 5, s = 0, d = 3, NILL = -1;
// Function to find the shortest path
// with minimum edges in a graph
static void Dijkstra(int [,] Graph, int _n, int _s, int _d)
{
int i, u, v, count;
int[] dist = new int[n];
int[] Blackened = new int[n];
int[] pathlength = new int[n];
int[] parent = new int[n];
// The parent Of the source vertex is always equal to nill
parent[_s] = NILL;
// first, we initialize all distances to infinity.
for (i = 0; i < n; i++)
dist[i] = INFINITY;
dist[_s] = 0;
for (count = 0; count < n - 1; count++)
{
u = MinDistance(dist, Blackened);
// if MinDistance() returns INFINITY, then the graph is not
// connected and we have traversed all of the vertices in the
// connected component of the source vertex, so it can reduce
// the time complexity sometimes
// In a directed graph, it means that the source vertex
// is not a root
if (u == INFINITY)
break;
else
{
// Mark the vertex as Blackened
Blackened[u] = 1;
for (v = 0; v < n; v++)
{
if (Blackened[v] == 0 && Graph[u,v] != 0
&& dist[u] + Graph[u,v] < dist[v])
{
parent[v] = u;
pathlength[v] = pathlength[parent[v]] + 1;
dist[v] = dist[u] + Graph[u,v];
}
else if (Blackened[v] == 0 && Graph[u,v] != 0
&& dist[u] + Graph[u,v] == dist[v]
&& pathlength[u] + 1 < pathlength[v])
{
parent[v] = u;
pathlength[v] = pathlength[u] + 1;
}
}
}
}
// Printing the path
if (dist[_d] != INFINITY)
PrintPath(parent, _d);
else
Console.Write("There is not path between vertex " +
_s + " to vertex " + _d);
}
static int MinDistance(int[] dist, int[] Blackened)
{
int min = INFINITY, min_index = -1, v;
for (v = 0; v < n; v++)
if (Blackened[v] == 0 && dist[v] < min)
{
min = dist[v];
min_index = v;
}
return min == INFINITY ? INFINITY : min_index;
}
// Function to print the path
static void PrintPath(int[] parent, int _d)
{
if (parent[_d] == NILL)
{
Console.Write(_d);
return;
}
PrintPath(parent, parent[_d]);
Console.Write("->" + _d);
}
// Driver Code
public static void Main()
{
// INFINITY means that u and v are not neighbors.
int [,] Graph = { { 0, 1, INFINITY, INFINITY, 10 },
{ 1, 0, 4, INFINITY, INFINITY },
{ INFINITY, 4, 0, 7, INFINITY },
{ INFINITY, INFINITY, 7, 0, 2 },
{ 10, INFINITY, INFINITY, 2, 0 } };
Dijkstra(Graph, n, s, d);
}
}
// This code is contributed by jana_sayantan.
0->4->3
Complejidad de tiempo: O(V^2) donde V es el número de vértices y E es el número de aristas.
Espacio Auxiliar: O(V + E)
Publicación traducida automáticamente
Artículo escrito por Shlomi Elhaiani y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA