(G, s)
| 111 | |
| 112 | |
| 113 | def dijk(G, s): |
| 114 | dist, known, path = {s: 0}, set(), {s: 0} |
| 115 | while True: |
| 116 | if len(known) == len(G) - 1: |
| 117 | break |
| 118 | mini = 100000 |
| 119 | for i in dist: |
| 120 | if i not in known and dist[i] < mini: |
| 121 | mini = dist[i] |
| 122 | u = i |
| 123 | known.add(u) |
| 124 | for v in G[u]: |
| 125 | if v[0] not in known: |
| 126 | if dist[u] + v[1] < dist.get(v[0], 100000): |
| 127 | dist[v[0]] = dist[u] + v[1] |
| 128 | path[v[0]] = u |
| 129 | for i in dist: |
| 130 | if i != s: |
| 131 | print(dist[i]) |
| 132 | |
| 133 | |
| 134 | """ |