Модификация Джикстра для получения кратчайшего пути от точки к точке

Question

У меня есть задача подсчитать количество кратчайшего пути от вершины до вершины в неориентированном графе весов. Я решил использовать алгоритм Джикстра, и я получил реализацию, и это правильно решает проблему, и это дает мне кратчайший путь. Я прочитал, что я должен изменить очередь, чтобы решить мою проблему, но когда я считаю путь там, как это.

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex]
            )
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    shortestPaths += 1
                    previous_vertices[neighbour] = current_vertex

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

Заранее спасибо

from collections import deque, namedtuple



inf = float('inf')
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges, both_ends=True):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))
        self.edges = []
        for edge in edges:
            self.add_edge(*edge, both_ends)

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex]
            )
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest

        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

graph = Graph([
    (1, 3, 2),  (1, 4, 2),  (3, 4 ,3), (1, 5, 12),
    (4, 2, 34), (5, 2, 24)]
)

print(graph.dijkstra(1,2))

Answer 1

Одна идея, которая приходит мне в голову, - это взять рабочую реализацию, которая возвращает только кратчайший путь, и подсчитывает количество маршрутов к каждой вершине во время распространения.

Я не уверен, является ли эта идея математически правильной хотя.

NB: вы можете Ctrl + F number_of_routes, чтобы найти мои модификации)

def dijkstra(self, source, dest):
    assert source in self.vertices, 'Such source node doesn\'t exist'
    distances = {vertex: inf for vertex in self.vertices}
    number_of_routes = {vertex: 0 for vertex in self.vertices}
    previous_vertices = {
        vertex: None for vertex in self.vertices
    }
    distances[source] = 0
    number_of_routes[source] = 1
    vertices = self.vertices.copy()

    while vertices:
        current_vertex = min(
            vertices, key=lambda vertex: distances[vertex]
        )
        vertices.remove(current_vertex)
        if distances[current_vertex] == inf:
            break
        for neighbour, cost in self.neighbours[current_vertex]:
            alternative_route = distances[current_vertex] + cost
            if alternative_route < distances[neighbour]:
                distances[neighbour] = alternative_route
                previous_vertices[neighbour] = current_vertex
                number_of_routes[neighbour] = number_of_routes[current_vertex]
                    # reset the counter as the previous routes were not optimal
            elif alternative_route == distances[neighbour]:
                number_of_routes[neighbour] += number_of_routes[current_vertex]

    path, current_vertex = deque(), dest

    while previous_vertices[current_vertex] is not None:
        path.appendleft(current_vertex)
        current_vertex = previous_vertices[current_vertex]
    if path:
        path.appendleft(current_vertex)
    return path, number_of_routes[dest]