Блог

Учитывая неориентированный граф G = (V, E) без отрицательных весов. Какова сложность проверки уникальности кратчайшего пути для каждой вершины в данном графе?

Вы также можете легко модифицировать алгоритмы кратчайшего пути, чтобы найти количество кратчайших путей. Например, рассмотрим этот код Дейкстры:

 def dijkstra(self, source, dest):
    assert source in self.vertices
    dist = {vertex: inf for vertex in self.vertices}
    previous = {vertex: None for vertex in self.vertices}
    dist[source] = 0
    q = self.vertices.copy()
    neighbours = {vertex: set() for vertex in self.vertices}
    for start, end, cost in self.edges:
        neighbours[start].add((end, cost))

    while q:
        u = min(q, key=lambda vertex: dist[vertex])
        q.remove(u)
        if dist[u] == inf or u == dest:
            break
        for v, cost in neighbours[u]:
            alt = dist[u]   cost
            if alt < dist[v]:                                  # Relax (u,v,a)
                dist[v] = alt
                previous[v] = u
 

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

 num_path = {vertex: 0 for vertex in self.vertices}
 

Затем на стадии расслабления, вместо того, чтобы проверять, меньше ли новое расстояние ( alt ), чем предыдущее расстояние, мы проверяем, равно ли оно тоже. Если оно равно, мы увеличиваем количество кратчайших путей для этого узла:

 if alt == dist[v]:
    num_path[v]  = 1
 

Когда мы находим новый кратчайший путь для узла, номер кратчайшего пути для нового узла равен номеру кратчайшего пути его родителя:

 if alt < distance:
    num_path[v] = num_path[u]
    ...
 

Итак, в конце концов, если num_path[v]==1 тогда мы можем сделать вывод, что существует единственный кратчайший путь от source до v .

Вот окончательный код:

 def dijkstra(self, source, dest):
    assert source in self.vertices
    dist = {vertex: inf for vertex in self.vertices}
    previous = {vertex: None for vertex in self.vertices}
    num_path = {vertex: 0 for vertex in self.vertices}
    dist[source] = 0
    num_path[source] = 1
    q = self.vertices.copy()
    neighbours = {vertex: set() for vertex in self.vertices}
    for start, end, cost in self.edges:
        neighbours[start].add((end, cost))

    while q:
        u = min(q, key=lambda vertex: dist[vertex])
        q.remove(u)
        if dist[u] == inf or u == dest:
            break
        for v, cost in neighbours[u]:
            alt = dist[u]   cost
            if alt < dist[v]:                                  # Relax (u,v,a)
                dist[v] = alt
                previous[v] = u
                num_path[v] = num_path[u]
            elif alt == dist[v]:
                num_path[v]  = 1
 

Таким образом, сложность будет равна сложности вашего алгоритма кратчайшего пути.