fork(3) download
copy 
  1. #https://i...content-available-to-author-only...e.com/l9RYCl
  2. #
  3. #Dijkstrov algoritmus na najdenie najkratsej cesty z jedneho vrcholu do vsetkych
  4. #
  5. #n m - rozmery, pocet vrcholov a hran
  6. #v1 v2 vzd - pre kazdu hranu 2 vrcholy a ich vzdialenost
  7. #v - pociatocny vrchol
  8.  
  9. import queue
  10.  
  11. n, m = [int(_) for _ in input().split()]
  12. susedia = {} #slovnik vrchol -> zoznam hran ako dvojica (vzdialenost, vrchol)
  13. vzdialenosti = {}
  14. for i in range(n): #pre vsetky vrcholy A,B,...
  15. 	x = chr(ord('A')+i) #i-te pismeno v poradi 
  16. 	susedia[x] = [] #prazdny zoznam susedov vrchola x
  17. 	vzdialenosti[x] = float('inf') #nekonecno
  18. print(susedia)
  19. print(vzdialenosti)
  20. for _ in range(m): #vsetky hrany
  21. 	v1, v2, vzd = [_ for _ in input().split()]
  22. 	vzd = int(vzd)
  23. 	susedia[v1].append( (vzd, v2) )
  24. 	susedia[v2].append( (vzd, v1) )
  25. v = input()
  26.  
  27. print(n, m)
  28. print(v)
  29. for s in susedia:
  30. 	print(s, susedia[s])
  31.  
  32. mesta = queue.PriorityQueue() #prioritny rad na vyber vzdy najmensej vzdialenosti
  33. mesta.put( (0, v) ) #zaciname vo vrchole v so vzdialenostou 0
  34. while not mesta.empty(): #pokial mame dalsie mesto na spracovanie
  35. 	vzd, mesto = mesta.get() #vyberieme dvojicu mesto a vzdialenost od pociatku
  36. 	print(vzd, mesto)
  37. 	if vzd < vzdialenosti[mesto]: #ak sme nasli kratsiu cestu
  38. 		vzdialenosti[mesto] = vzd #aktualizujeme na novu, kratsiu, vzdialenost
  39. 		for sused in susedia[mesto]: #pridame hrany k susedom
  40. 			#sused je dvojica (vzdialenost, vrchol)
  41. 			print(sused)
  42. 			mesta.put( (vzd+sused[0], sused[1]) ) #pridame novu vzdialenost k susedovi
  43. print(vzdialenosti)
Success #stdin #stdout 0.02s 28136KB
comments (?)
stdin
copy 
7 11
A B 7
A D 5
B C 8
B D 9
B E 7
C E 5
D E 15
D F 6
E F 8
E G 9
F G 11
A
stdout
copy 
{'D': [], 'C': [], 'F': [], 'E': [], 'A': [], 'G': [], 'B': []}
{'D': inf, 'C': inf, 'F': inf, 'E': inf, 'A': inf, 'G': inf, 'B': inf}
7 11
A
D [(5, 'A'), (9, 'B'), (15, 'E'), (6, 'F')]
C [(8, 'B'), (5, 'E')]
F [(6, 'D'), (8, 'E'), (11, 'G')]
E [(7, 'B'), (5, 'C'), (15, 'D'), (8, 'F'), (9, 'G')]
A [(7, 'B'), (5, 'D')]
G [(9, 'E'), (11, 'F')]
B [(7, 'A'), (8, 'C'), (9, 'D'), (7, 'E')]
0 A
(7, 'B')
(5, 'D')
5 D
(5, 'A')
(9, 'B')
(15, 'E')
(6, 'F')
7 B
(7, 'A')
(8, 'C')
(9, 'D')
(7, 'E')
10 A
11 F
(6, 'D')
(8, 'E')
(11, 'G')
14 A
14 B
14 E
(7, 'B')
(5, 'C')
(15, 'D')
(8, 'F')
(9, 'G')
15 C
(8, 'B')
(5, 'E')
16 D
17 D
19 C
19 E
20 E
20 E
21 B
22 F
22 G
(9, 'E')
(11, 'F')
23 B
23 G
29 D
31 E
33 F
{'D': 5, 'C': 15, 'F': 11, 'E': 14, 'A': 0, 'G': 22, 'B': 7}
https://ideone.com/l9RYCl
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!