fork download
copy 
  1. #https://i...content-available-to-author-only...e.com/g0uzuw
  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. 			if vzd+sused[0] < vzdialenosti[sused[1]]: #vloz iba ak je to kratsie!
  43. 				mesta.put( (vzd+sused[0], sused[1]) ) #pridame novu vzdialenost k susedovi
  44. print(vzdialenosti)
Success #stdin #stdout 0.02s 28072KB
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
D
stdout
copy 
{'A': [], 'E': [], 'B': [], 'D': [], 'F': [], 'C': [], 'G': []}
{'A': inf, 'E': inf, 'B': inf, 'D': inf, 'F': inf, 'C': inf, 'G': inf}
7 11
D
A [(7, 'B'), (5, 'D')]
E [(7, 'B'), (5, 'C'), (15, 'D'), (8, 'F'), (9, 'G')]
B [(7, 'A'), (8, 'C'), (9, 'D'), (7, 'E')]
D [(5, 'A'), (9, 'B'), (15, 'E'), (6, 'F')]
F [(6, 'D'), (8, 'E'), (11, 'G')]
C [(8, 'B'), (5, 'E')]
G [(9, 'E'), (11, 'F')]
0 D
5 A
6 F
9 B
12 B
14 E
15 E
16 E
17 C
17 G
19 C
23 G
{'A': 5, 'E': 14, 'B': 9, 'D': 0, 'F': 6, 'C': 17, 'G': 17}
https://ideone.com/g0uzuw
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!