Взвешенный кратчайший путь Дейкстры в 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: Пожалуйста, простите меня, если я напечатал или не смог правильно объяснить, поскольку я новичок в этом мире и стараюсь изо всех сил.

Шаблоны Angular PrimeNg
Шаблоны Angular PrimeNg
Как привнести проверку типов в наши шаблоны Angular, использующие компоненты библиотеки PrimeNg, и настроить их отображение с помощью встроенной...
Создайте ползком, похожим на звездные войны, с помощью CSS и Javascript
Создайте ползком, похожим на звездные войны, с помощью CSS и Javascript
Если вы веб-разработчик (или хотите им стать), то вы наверняка гик и вам нравятся "Звездные войны". А как бы вы хотели, чтобы фоном для вашего...
Документирование API с помощью Swagger на Springboot
Документирование API с помощью Swagger на Springboot
В предыдущей статье мы уже узнали, как создать Rest API с помощью Springboot и MySql .
Начала с розового дизайна
Начала с розового дизайна
Pink Design - это система дизайна Appwrite с открытым исходным кодом для создания последовательных и многократно используемых пользовательских...
Шлюз в PHP
Шлюз в PHP
API-шлюз (AG) - это сервер, который действует как единая точка входа для набора микросервисов.
14 Задание: Типы данных и структуры данных Python для DevOps
14 Задание: Типы данных и структуры данных Python для DevOps
проверить тип данных используемой переменной, мы можем просто написать: your_variable=100
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

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

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