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 una 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 rutas más cortas) que realice un seguimiento de los vértices incluidos en el árbol de rutas más cortas, 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:
- Elija un vértice u que no esté en sptSet y tenga un valor de distancia mínimo.
- Incluya u en sptSet .
- Actualice el valor de 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 de un 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.
Python3
# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
def printSolution(self, dist):
print("Vertex \t Distance from Source")
for node in range(self.V):
print(node, "\t\t", dist[node])
# A utility function to find the vertex with
# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minDistance(self, dist, sptSet):
# Initialize minimum distance for next node
min = 1e7
# Search not nearest vertex not in the
# shortest path tree
for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v
return min_index
# Function that implements Dijkstra's single source
# shortest path algorithm for a graph represented
# using adjacency matrix representation
def dijkstra(self, src):
dist = [1e7] * self.V
dist[src] = 0
sptSet = [False] * self.V
for cout in range(self.V):
# Pick the minimum distance vertex from
# the set of vertices not yet processed.
# u is always equal to src in first iteration
u = self.minDistance(dist, sptSet)
# Put the minimum distance vertex in the
# shortest path tree
sptSet[u] = True
# Update dist value of the adjacent vertices
# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shortest path tree
for v in range(self.V):
if (self.graph[u][v] > 0 and
sptSet[v] == False and
dist[v] > dist[u] + self.graph[u][v]):
dist[v] = dist[u] + self.graph[u][v]
self.printSolution(dist)
# Driver program
g = Graph(9)
g.graph = [[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]
]
g.dijkstra(0)
# This code is contributed by Divyanshu Mehta
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