Dado un gráfico y un vértice de origen en el gráfico, encuentre los caminos más cortos desde el origen hasta todos los vértices en el gráfico dado.
El algoritmo de Dijkstra es muy similar al algoritmo de Prim para el árbol de expansión mínimo . Al igual que el MST de Prim, generamos un SPT (árbol de ruta más corta) con la fuente dada como raíz. Mantenemos dos conjuntos, un conjunto contiene vértices incluidos en el árbol de ruta más corta, otro conjunto incluye vértices que aún no están incluidos en el árbol de ruta más corta. En cada paso del algoritmo, encontramos un vértice que está en el otro conjunto (conjunto de aún no incluido) y tiene una distancia mínima de la fuente.
A continuación se detallan los pasos utilizados en el algoritmo de Dijkstra para encontrar el camino más corto desde un único vértice fuente a todos los demás vértices en el gráfico dado.
Algoritmo
1) Cree un conjunto sptSet (conjunto de árboles de ruta más corta) que realiza un seguimiento de los vértices incluidos en el árbol de ruta más corta, es decir, cuya distancia mínima desde la fuente se calcula y finaliza. Inicialmente, este conjunto está vacío.
2) Asigne un valor de distancia a todos los vértices en el gráfico de entrada. Inicialice todos los valores de distancia como INFINITOS. Asigne el valor de distancia como 0 para el vértice de origen para que se elija primero.
3) Mientras que sptSet no incluye todos los vértices
…. a) Elija un vértice u que no esté en sptSety tiene un valor mínimo de distancia.
…. b) Incluya u en sptSet .
…. c) Actualice el valor de la distancia de todos los vértices adyacentes de u. Para actualizar los valores de distancia, itere a través de todos los vértices adyacentes. Para cada vértice adyacente v, si la suma del valor de distancia de u (desde la fuente) y el peso del borde uv es menor que el valor de distancia de v, entonces actualice el valor de distancia de v.
C#
// A C# program for Dijkstra's single
// source shortest path algorithm.
// The program is for adjacency matrix
// representation of the graph
using System;
class GFG {
// A utility function to find the
// vertex with minimum distance
// value, from the set of vertices
// not yet included in shortest
// path tree
static int V = 9;
int minDistance(int[] dist,
bool[] sptSet)
{
// Initialize min value
int min = int.MaxValue, min_index = -1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min) {
min = dist[v];
min_index = v;
}
return min_index;
}
// A utility function to print
// the constructed distance array
void printSolution(int[] dist, int n)
{
Console.Write("Vertex Distance "
+ "from Source\n");
for (int i = 0; i < V; i++)
Console.Write(i + " \t\t " + dist[i] + "\n");
}
// Function that implements Dijkstra's
// single source shortest path algorithm
// for a graph represented using adjacency
// matrix representation
void dijkstra(int[, ] graph, int src)
{
int[] dist = new int[V]; // The output array. dist[i]
// will hold the shortest
// distance from src to i
// sptSet[i] will true if vertex
// i is included in shortest path
// tree or shortest distance from
// src to i is finalized
bool[] sptSet = new bool[V];
// Initialize all distances as
// INFINITE and stpSet[] as false
for (int i = 0; i < V; i++) {
dist[i] = int.MaxValue;
sptSet[i] = false;
}
// Distance of source vertex
// from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex
// from the set of vertices not yet
// processed. u is always equal to
// src in first iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent
// vertices of the picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in
// sptSet, there is an edge from u
// to v, and total weight of path
// from src to v through u is smaller
// than current value of dist[v]
if (!sptSet[v] && graph[u, v] != 0 &&
dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v])
dist[v] = dist[u] + graph[u, v];
}
// print the constructed distance array
printSolution(dist, V);
}
// Driver Code
public static void Main()
{
/* Let us create the example
graph discussed above */
int[, ] graph = new int[, ] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
GFG t = new GFG();
t.dijkstra(graph, 0);
}
}
// This code is contributed by ChitraNayal
Vertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14
Consulte el artículo completo sobre el algoritmo de ruta más corta de Dijkstra | Codicioso Algo-7 para más detalles!
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