Para el algoritmo de Dijkstra, ¿cuál sería una forma de mantener y almacenar los vértices que contiene cada camino más corto?

16 Jun, 2023 Programación 0

Lo he codificado para actualizar todos los costos de los bordes y similares para completar el objetivo principal de Dijkstra de encontrar el camino más corto desde el vértice fuente a todos los demás vértices.

Pero lo que necesito ayuda para descubrir es una forma de almacenar los vértices que cada camino más corto contiene en una matriz que contiene los vértices de cada camino que pasó a través de él.

Por ejemplo, digamos que el camino más corto desde el vértice fuente (A) al vértice (Z) es
A -> B -> V -> Z. El camino más corto pasa por los vértices B y V en orden para llegar a Z. Quiero poder almacenar cada uno de los vértices en esa secuencia en una matriz. Luego, coloque esa matriz en una lista más grande de matrices que contendrá todas las secuencias. El problema es que no estoy seguro de dónde colocar eso ya que el bucle while a continuación es para actualizar los costos de los bordes.

from queue import PriorityQueue

class Graph:

    def __init__(self, num_of_vertices):
        self.v = num_of_vertices
        self.edges = [[-1 for i in range(num_of_vertices)] for j in range(num_of_vertices)]
        self.visited = []

    def add_edge(self, u, v, weight):
        self.edges[u][v] = weight
        self.edges[v][u] = weight

    def dijkstra(self, start_vertex):
        D = {v:float('inf') for v in range(self.v)}
        V = {v:None for v in range(self.v)}
        D[start_vertex] = 0

        pq = PriorityQueue()
        pq.put((0, start_vertex))

        AllPathsList = []

        while not pq.empty():
            (dist, current_vertex) = pq.get()
            self.visited.append(current_vertex)

            for neighbor in range(self.v):
                if self.edges[current_vertex][neighbor] != -1:
                    distance = self.edges[current_vertex][neighbor]
                    if neighbor not in self.visited:
                        old_cost = D[neighbor]
                        new_cost = D[current_vertex] + distance
                        if new_cost < old_cost:
                            pq.put((new_cost, neighbor))
                            D[neighbor] = new_cost
                            V[neighbor] = current_vertex          
            S = []
            u = current_vertex
            while V[u] != None:
                S.insert(0, u)
                u = V[u]

            S.insert(0, start_vertex)
            AllPathsList.append(S)

        return D, AllPathsList

def main():
    g = Graph(6)
    g.add_edge(0, 1, 4)
    g.add_edge(0, 2, 7)
    g.add_edge(1, 2, 11)
    g.add_edge(1, 3, 20)
    g.add_edge(3, 4, 5)
    g.add_edge(3, 5, 6)
    g.add_edge(2, 3, 3)
    g.add_edge(2, 4 ,2)

    D, AllPathsList = g.dijkstra(0)

    for vertex in range(len(D)):
        print("La distancia desde el vértice 0 al vértice", vertex, "es:", D[vertex])
        print("Ruta particular: ", AllPathsList[vertex])

main()

davy.ai

June 16, 2023 at 2:50 pm

Para almacenar los vértices en la secuencia de cada camino más corto, se puede utilizar un diccionario para hacer un seguimiento del padre de cada vértice en el camino más corto. El padre de un vértice es el vértice que se utilizó para llegar a ese vértice en el camino más corto. Se puede actualizar el padre de cada vértice vecino cuando se actualiza el costo del vértice vecino en el bucle while.

Después de haber actualizado el costo del vértice vecino, se puede comprobar si tiene un vértice padre. Si lo tiene, entonces se puede actualizar su padre para que sea el vértice actual. Si no lo tiene, entonces se puede establecer su padre para que sea el vértice actual. Esto asegurará que se haga un seguimiento del padre de cada vértice en el camino más corto.

Una vez que se haya encontrado el camino más corto hacia un vértice, se puede utilizar el diccionario de padres para retroceder desde el vértice de destino hasta el vértice de origen, y almacenar los vértices en la secuencia del camino más corto. Se puede añadir cada secuencia a una lista más grande de secuencias que contendrá todos los caminos más cortos.

Aquí está el código actualizado:

from queue import PriorityQueue


class Grafo:
    def __init__(self, num_de_vértices):
        self.v = num_de_vértices
        self.aristas = [[-1 for i in range(num_de_vértices)] for j in range(num_de_vértices)]
        self.visitado = []

    def añadir_arista(self, u, v, peso):
        self.aristas[u][v] = peso
        self.aristas[v][u] = peso

    def dijkstra(self, vértice_inicial):
        D = {v: float('inf') for v in range(self.v)}
        padres = {v: None for v in range(self.v)}
        D[vértice_inicial] = 0

        cola_prioridad = PriorityQueue()
        cola_prioridad.put((0, vértice_inicial))

        todos_los_caminos = []

        while not cola_prioridad.empty():
            (distancia, vértice_actual) = cola_prioridad.get()
            self.visitado.append(vértice_actual)

            for vecino in range(self.v):
                if self.aristas[vértice_actual][vecino] != -1:
                    distancia_vecino = self.aristas[vértice_actual][vecino]
                    if vecino not in self.visitado:
                        costo_viejo = D[vecino]
                        costo_nuevo = D[vértice_actual] + distancia_vecino
                        if costo_nuevo < costo_viejo:
                            cola_prioridad.put((costo_nuevo, vecino))
                            D[vecino] = costo_nuevo
                            padres[vecino] = vértice_actual

            if vértice_actual == vértice_inicial or padres[vértice_actual] is not None:
                camino = [vértice_actual]
                while camino[-1] != vértice_inicial and camino[-1] is not None:
                    camino.append(padres[camino[-1]])
                camino.reverse()
                todos_los_caminos.append(camino)

        return D, todos_los_caminos


def main():
    g = Grafo(6)
    g.añadir_arista(0, 1, 4)
    g.añadir_arista(0, 2, 7)
    g.añadir_arista(1, 2, 11)
    g.añadir_arista(1, 3, 20)
    g.añadir_arista(3, 4, 5)
    g.añadir_arista(3, 5, 6)
    g.añadir_arista(2, 3, 3)
    g.añadir_arista(2, 4, 2)

    D, todos_los_caminos = g.dijkstra(0)

    for vértice in range(len(D)):
        print("La distancia desde el vértice 0 hasta el vértice", vértice, "es:", D[vértice])
        print("El camino particular es:", todos_los_caminos[vértice])


main()

En el código actualizado, el diccionario padres se utiliza para almacenar el padre de cada vértice en el camino más corto. La variable camino se utiliza para almacenar la secuencia de vértices en cada camino más corto. La variable camino se añade a la lista todos_los_caminos que contendrá todos los caminos más cortos para cada vértice.

es.davy.ai

¿Tienes una pregunta?

Para el algoritmo de Dijkstra, ¿cuál sería una forma de mantener y almacenar los vértices que contiene cada camino más corto?

Answer

davy.ai