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