Dijkstra algorithm Examples: >>> graph_test = Graph(3) >>> graph_test.add_edge(0, 1, 2) >>> graph_test.add_edge(1, 2, 2) >>> graph_test.dijkstra(0) Distance from node: 0 Node 0 has distance: 0 Node 1 has distance: 2 No
(self, src)
| 275 | print(u, "->", " -> ".join(str(f"{v}({w})") for v, w in self.adjList[u])) |
| 276 | |
| 277 | def dijkstra(self, src): |
| 278 | """ |
| 279 | Dijkstra algorithm |
| 280 | |
| 281 | Examples: |
| 282 | >>> graph_test = Graph(3) |
| 283 | >>> graph_test.add_edge(0, 1, 2) |
| 284 | >>> graph_test.add_edge(1, 2, 2) |
| 285 | >>> graph_test.dijkstra(0) |
| 286 | Distance from node: 0 |
| 287 | Node 0 has distance: 0 |
| 288 | Node 1 has distance: 2 |
| 289 | Node 2 has distance: 4 |
| 290 | >>> graph_test.dist |
| 291 | [0, 2, 4] |
| 292 | |
| 293 | >>> graph_test = Graph(2) |
| 294 | >>> graph_test.add_edge(0, 1, 2) |
| 295 | >>> graph_test.dijkstra(0) |
| 296 | Distance from node: 0 |
| 297 | Node 0 has distance: 0 |
| 298 | Node 1 has distance: 2 |
| 299 | >>> graph_test.dist |
| 300 | [0, 2] |
| 301 | |
| 302 | >>> graph_test = Graph(3) |
| 303 | >>> graph_test.add_edge(0, 1, 2) |
| 304 | >>> graph_test.dijkstra(0) |
| 305 | Distance from node: 0 |
| 306 | Node 0 has distance: 0 |
| 307 | Node 1 has distance: 2 |
| 308 | Node 2 has distance: 0 |
| 309 | >>> graph_test.dist |
| 310 | [0, 2, 0] |
| 311 | |
| 312 | >>> graph_test = Graph(3) |
| 313 | >>> graph_test.add_edge(0, 1, 2) |
| 314 | >>> graph_test.add_edge(1, 2, 2) |
| 315 | >>> graph_test.add_edge(0, 2, 1) |
| 316 | >>> graph_test.dijkstra(0) |
| 317 | Distance from node: 0 |
| 318 | Node 0 has distance: 0 |
| 319 | Node 1 has distance: 2 |
| 320 | Node 2 has distance: 1 |
| 321 | >>> graph_test.dist |
| 322 | [0, 2, 1] |
| 323 | |
| 324 | >>> graph_test = Graph(4) |
| 325 | >>> graph_test.add_edge(0, 1, 4) |
| 326 | >>> graph_test.add_edge(1, 2, 2) |
| 327 | >>> graph_test.add_edge(2, 3, 1) |
| 328 | >>> graph_test.add_edge(0, 2, 3) |
| 329 | >>> graph_test.dijkstra(0) |
| 330 | Distance from node: 0 |
| 331 | Node 0 has distance: 0 |
| 332 | Node 1 has distance: 4 |
| 333 | Node 2 has distance: 3 |
| 334 | Node 3 has distance: 4 |
no test coverage detected