dijk({1: [(2, 7), (3, 9), (6, 14)], 2: [(1, 7), (3, 10), (4, 15)], 3: [(1, 9), (2, 10), (4, 11), (6, 2)], 4: [(2, 15), (3, 11), (5, 6)], 5: [(4, 6), (6, 9)], 6: [(1, 14), (3, 2), (5, 9)]}, 1) 7 9 11 20 20
(g, s)
| 147 | |
| 148 | |
| 149 | def dijk(g, s): |
| 150 | """ |
| 151 | dijk({1: [(2, 7), (3, 9), (6, 14)], |
| 152 | 2: [(1, 7), (3, 10), (4, 15)], |
| 153 | 3: [(1, 9), (2, 10), (4, 11), (6, 2)], |
| 154 | 4: [(2, 15), (3, 11), (5, 6)], |
| 155 | 5: [(4, 6), (6, 9)], |
| 156 | 6: [(1, 14), (3, 2), (5, 9)]}, 1) |
| 157 | 7 |
| 158 | 9 |
| 159 | 11 |
| 160 | 20 |
| 161 | 20 |
| 162 | """ |
| 163 | dist, known, path = {s: 0}, set(), {s: 0} |
| 164 | while True: |
| 165 | if len(known) == len(g) - 1: |
| 166 | break |
| 167 | mini = 100000 |
| 168 | for key, value in dist: |
| 169 | if key not in known and value < mini: |
| 170 | mini = value |
| 171 | u = key |
| 172 | known.add(u) |
| 173 | for v in g[u]: |
| 174 | if v[0] not in known and dist[u] + v[1] < dist.get(v[0], 100000): |
| 175 | dist[v[0]] = dist[u] + v[1] |
| 176 | path[v[0]] = u |
| 177 | for key, value in dist.items(): |
| 178 | if key != s: |
| 179 | print(value) |
| 180 | |
| 181 | |
| 182 | """ |