graphs.dijkstra_2

Attributes

V

Functions

dijkstra(→ None)	Runs Dijkstra's algorithm and prints distances.
min_dist(mdist, vset, v)	Returns the vertex with the minimum distance from the source vertex
print_dist(→ None)	Print vertex distances.

Module Contents

graphs.dijkstra_2.dijkstra(graph, v, src) → None

Runs Dijkstra’s algorithm and prints distances.

Calculate the shortest path from source to all other vertices using Dijkstra’s algorithm.

>>> g = [
...     [0.0, 5.0, float('inf'), 10.0],
...     [float('inf'), 0.0, 3.0, float('inf')],
...     [float('inf'), float('inf'), 0.0, 1.0],
...     [float('inf'), float('inf'), float('inf'), 0.0],
... ]
>>> dijkstra(g, 4, 0)
Vertex Distance
0    0
1    5
2    8
3    9
>>> g2 = [
...     [0.0, float('inf')],
...     [float('inf'), 0.0],
... ]
>>> dijkstra(g2, 2, 0)
Vertex Distance
0    0
1    INF
>>> dijkstra([[0.0]], 1, 0)
Vertex Distance
0    0
>>> graph = [[0.0, 1.0, 6.0],                [float("inf"), 0.0, 3.0],                [float("inf"), float("inf"), 0.0]]
>>> dijkstra(graph, 3, 0)
Vertex Distance
0    0
1    1
2    4

graphs.dijkstra_2.min_dist(mdist, vset, v)

Returns the vertex with the minimum distance from the source vertex that has not yet been visited.

>>> min_dist([0, 4, 2, float('inf')], [True, False, False, False], 4)
2
>>> min_dist([0, 4, 2, 1], [True, False, True, False], 4)
3
>>> min_dist([0, 4, 2, 1], [True, True, True, True], 4)
-1
>>> min_dist([float('inf'), float('inf')], [False, False], 2)
-1
>>> min_dist([0, 1, 6], [True, False, False], 3)
1

graphs.dijkstra_2.print_dist(dist, v) → None

Print vertex distances. >>> print_dist([0.0, 5.0, 8.0, 9.0], 4) Vertex Distance 0 0 1 5 2 8 3 9 >>> print_dist([0.0, float(‘inf’)], 2) Vertex Distance 0 0 1 INF >>> print_dist([0.0], 1) Vertex Distance 0 0

graphs.dijkstra_2.V