Как найти несколько кратчайших путей с Дейкстрой за одну итерацию?

Question

В настоящее время у меня есть работающий алгоритм Дейкстры, но я хочу найти несколько кратчайших путей на одной и той же «карте» (одни и те же препятствия и т. Д.), Каждый раз с одной и той же начальной точкой (поэтому просто разные конечные точки). Прямо сейчас мне пришлось бы запускать алгоритм несколько раз, чтобы получить все пути, даже если (если я правильно понимаю алгоритм), я уже должен был получить эту информацию, запустив алгоритм только один раз. Как бы я реализовал это в моем коде? (Как получить несколько путей, просто запустив Dijkstra один раз?)

Я попытался найти способ, чтобы в качестве входных данных использовались многоплановые конечные местоположения, не совсем нашел способ сделать это.

def dijsktra(graph, initial, end):
    # shortest paths is a dict of nodes
    # whose value is a tuple of (previous node, weight)
    shortest_paths = {initial: (None, 0)}
    current_node = initial
    visited = set()

    while current_node != end:
        visited.add(current_node)
        destinations = graph.edges[current_node]
        weight_to_current_node = shortest_paths[current_node][1]

        for next_node in destinations:
            weight = graph.weights[(current_node, next_node)] + weight_to_current_node

            if len(shortest_paths) >= 2:
                #print(shortest_paths[-1], shortest_paths[-2])
                pass

            if next_node not in shortest_paths:
                shortest_paths[next_node] = (current_node, weight)
                #print(destinations,  shortest_paths[next_node])
            else:
                current_shortest_weight = shortest_paths[next_node][1]
                if current_shortest_weight > weight:
                    shortest_paths[next_node] = (current_node, weight)

        next_destinations = {node: shortest_paths[node] for node in
                                shortest_paths if node not in visited}
        if not next_destinations:
            return "Route Not Possible"
        # next node is the destination with the lowest weight
        current_node = min(next_destinations, key=lambda k: next_destinations[k][1])

    # Work back through destinations in shortest path
    path = []
    while current_node is not None:
        path.append(current_node)
        next_node = shortest_paths[current_node][0]
        current_node = next_node
    # Reverse path
    path = path[::-1]
    return path

Итак, я звоню так:

for location in end_locations:
    path = dijkstra(graph, start, location)

Я хочу позвонить так:

paths = dijkstra(graph, start, end_locations)

Вот класс графика из-за запроса в комментариях:

class Graph():
    def __init__(self):
        """
        self.edges is a dict of all possible next nodes
        e.g. {'X': ['A', 'B', 'C', 'E'], ...}
        self.weights has all the weights between two nodes,
        with the two nodes as a tuple as the key
        e.g. {('X', 'A'): 7, ('X', 'B'): 2, ...}
        """
        self.edges = defaultdict(list)
        self.weights = {}

    def add_edge(self, from_node, to_node, weight):
        # Note: assumes edges are bi-directional
        self.edges[from_node].append(to_node)
        self.edges[to_node].append(from_node)
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight

Мне нужно, чтобы выходные данные были множественными путями, но сейчас он работает только с одним.

Answer 1

Не останавливайтесь, когда вы достигнете конца, но когда вы достигли каждого ожидаемого места. Каждый раз, когда вы достигли местоположения, сохраняйте путь.

def dijsktra(graph, initial, ends):
    # shortest paths is a dict of nodes
    # whose value is a tuple of (previous node, weight)
    shortest_paths = {initial: (None, 0)}
    current_node = initial
    visited = set()
    node_to_visit = ends.copy()
    paths = []

    while node_to_visit:
        visited.add(current_node)
        destinations = graph.edges[current_node]
        weight_to_current_node = shortest_paths[current_node][1]

        for next_node in destinations:
            weight = graph.weights[(current_node, next_node)] + weight_to_current_node

            if len(shortest_paths) >= 2:
                # print(shortest_paths[-1], shortest_paths[-2])
                pass

            if next_node not in shortest_paths:
                shortest_paths[next_node] = (current_node, weight)
                # print(destinations,  shortest_paths[next_node])
            else:
                current_shortest_weight = shortest_paths[next_node][1]
                if current_shortest_weight > weight:
                    shortest_paths[next_node] = (current_node, weight)

        next_destinations = {node: shortest_paths[node] for node in
                             shortest_paths if node not in visited}
        if not next_destinations:
            return "Route Not Possible"
        # next node is the destination with the lowest weight
        current_node = min(next_destinations, key=lambda k: next_destinations[k][1])
        if current_node in node_to_visit:
            node_to_visit.remove(current_node)
            # Work back through destinations in shortest path
            path = []
            last_node = current_node
            while last_node is not None:
                path.append(last_node)
                next_node = shortest_paths[last_node][0]
                last_node = next_node
            # Reverse path
            path = path[::-1]
            paths.append(path)
    return paths