Взвешенный кратчайший путь Дейкстры в Python

Я пытаюсь решить вопрос из PepCoding, Graph Foundation 1, Shortest Path In Weights и реплицировать решение с Java на Python.

Вопрос:

1. You are given a graph and a source vertex. The vertices represent cities and the edges represent 
    distance in kms.
2. You are required to find the shortest path to each city (in terms of kms) from the source city along 
    with the total distance on path from source to destinations.

Note -> For output, check the sample output and question video.

Пример ввода:

7
9
0 1 10
1 2 10
2 3 10
0 3 40
3 4 2
4 5 3
5 6 3
4 6 8
2 5 5
0

Вывод:

0 via 0 @ 0
1 via 01 @ 10
2 via 012 @ 20
5 via 0125 @ 25
4 via 01254 @ 28
6 via 01256 @ 28
3 via 012543 @ 30

Я реализовал список вместо PriorityQueue и попытался отсортировать элемент Pair в классе с помощью таких операторов, как __lt__ и __ge__ . Тем не менее, я получал все результаты правильно, за исключением того, что кратчайший путь между 0 и 3 неверен.

Это мой вывод:

0  via  0 @ 0
1  via  01 @ 10
2  via  012 @ 20
5  via  0125 @ 25
4  via  01254 @ 28
6  via  01256 @ 28
3  via  0123 @ 30  <-- This differ should be: 3 via 012543 @ 30
Loop:  [(28, 6, '01256'), (30, 3, '0123'), (40, 3, '03'), (30, 3, '012543')]
Loop:  [(28, 6, '01256'), (30, 3, '0123'), (40, 3, '03'), (30, 3, '012543'), (36, 6, '012546')]
POP:  (28, 6, '01256')
6  via  01256 @ 28
POP:  (30, 3, '0123')  <-- *This is getting pop instead of, POP:  (30, 3, '012543')
3  via  0123 @ 30
POP:  (30, 3, '012543')
POP:  (36, 6, '012546')
POP:  (40, 3, '03')

Этот код на Java, где реализован compareTo, имеет значение.

static class Pair implements Comparable<Pair> {
      int v;
      String psf;
      int wsf;

      Pair(int v, String psf, int wsf){
         this.v = v;
         this.psf = psf;
         this.wsf = wsf;
      }

      public int compareTo(Pair o){
         return this.wsf - o.wsf;
      }
   }

Вот код на Python:


class Edge:
    def __init__(self, src, nbr, wt):
        self.src = src
        self.nbr = nbr
        self.wt = wt

    def __repr__(self):
        return repr(self.__dict__)


class Pair:
    def __init__(self, wsf, v, psf):
        self.wsf = wsf
        self.v = v
        self.psf = psf

    def __repr__(self):
        return repr((self.wsf, self.v, self.psf))

    def __lt__(self, o):
        return self.wsf < o.wsf

    def __ge__(self, o):
        return len(self.psf) < len(o.psf)


def main():
    vtces = int(input())
    edges = int(input())
    graph = {}
    for i in range(vtces):
        graph[i] = []

    for i in range(edges):
        lines = input().split(" ")
        v1 = int(lines[0])
        v2 = int(lines[1])
        wt = int(lines[2])
        e1 = Edge(v1, v2, wt)
        e2 = Edge(v2, v1, wt)
        graph[e1.src].append(e1)
        graph[e2.src].append(e2)

    src = int(input())
    # print(type(graph))
    # for i in graph:
    #     for j in graph[i]:
    #         print(i, j)

    # Write your code here
    pq = []

    pq.append(Pair(0, src, str(src) + ""))
    # print("\nStart: ",pq)
    visited = [False] * vtces

    while len(pq) > 0:
        pq.sort()
        rem = pq.pop(0)
        # print("POP: ", rem)

        if visited[rem.v] == True:
            continue
        visited[rem.v] = True
        print(rem.v, " via ", rem.psf, "@", rem.wsf)

        for e in graph[rem.v]:
            if visited[e.nbr] == False:
                pq.append(Pair(rem.wsf + e.wt, e.nbr, str(rem.psf) + str(e.nbr)))
                # print("Loop: ",pq)

    # print(pq)


if __name__ == "__main__":
    main()

PS: Пожалуйста, простите меня, если я напечатал или не смог правильно объяснить, поскольку я новичок в этом мире и стараюсь изо всех сил.

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
0
114
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Посмотрев на ваш код, я думаю, что функция сортировки вернет путь с кратчайшим расстоянием и минимальным количеством прыжков (вершин).

Спасибо за ваше время, цените его. Тем не менее, функция сортировки возвращает отсортированный порядок, но не может получить максимальную длину пути. POP: (30, 3, '0123') <-- * Это всплывает вместо POP: (30, 3, '012543') 3 через 0123 @ 30 POP: (30, 3, '012543') << ожидал, что это будет index 0. POP: (36, 6, '012546')POP: (40, 3, '03') Я пытаюсь заставить функцию сортировки выполнять (сортировать) минимальный вес и максимальное количество вершин или максимальное количество ребер.

imeanup 19.11.2022 10:00
Ответ принят как подходящий

После попытки компаратора нескольких классов или Java «compareTo()», как упоминалось здесь . Наконец, я наткнулся на «Python-эквивалент Java compareTo()» здесь и сделал следующую модификацию в классе Pair, и это решило путь для 3 via 012543 @ 30 [Предыдущая ошибка была 30, 3, '0123'].

class Pair():
    def __init__(self, wsf, v, psf):
        self.wsf = wsf
        self.v = v
        self.psf = psf

    def __repr__(self):
        return repr((self.wsf, self.v, self.psf))

    def __lt__(self, other):
        if self.wsf == other.wsf:
            return len(self.psf) > len(other.psf)
        return self.wsf < other.wsf

    def __gt__(self, other):
        return other.__lt__(self)

Я реализовал вышеописанное с помощью list, но во время тестирования попробовал heapq, что не помогло. Может быть, я не уверен в лучшем способе.

while len(pq) > 0:
        pq.sort()
        # print("sLoop: ", pq)
        rem = pq.pop(0)
        # print("POP: ", rem)

        if visited[rem.v] == True:
            continue
        visited[rem.v] = True
        print(rem.v, "via", rem.psf, "@", rem.wsf)

        for e in graph[rem.v]:
            if visited[e.nbr] == False:
                pq.append(Pair(rem.wsf + e.wt, e.nbr, str(rem.psf) + str(e.nbr)))
                # print("Loop: ", pq)

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

Кроме того, приведенный ниже тестовый пример терпит неудачу, и я не уверен, каковы ожидаемые выходные/входные данные в тестовом примере (поскольку возможны несколько ребер):

2 via 2 @ 0
5 via 25 @ 5
4 via 254 @ 8
6 via 256 @ 8
3 via 2543 @ 10
1 via 21 @ 10
0 via 210 @ 20

Но все равно я довольна своим результатом. Спасибо всем.

Другие вопросы по теме