8000 Dijkstra, single-source shortest paths. · anubhavcoder/practice-python@b62825d · GitHub
[go: up one dir, main page]
Skip to content

Commit b62825d

Browse files
jwashamjwasham
committed
Dijkstra, single-source shortest paths.
1 parent c5d765d commit b62825d

File tree

2 files changed

+128
-0
lines changed

2 files changed

+128
-0
lines changed

‎graphs/dijkstra.py

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
import queue
10000 2+
from collections import namedtuple
3+
4+
Edge = namedtuple('Edge', ['vertex', 'weight'])
5+
6+
7+
class GraphWeighted(object):
8+
def __init__(self, vertex_count):
9+
self.vertex_count = vertex_count
10+
self.adjacency_list = [[] for _ in range(vertex_count)]
11+
12+
def add_edge(self, source, dest, weight):
13+
assert source < self.vertex_count
14+
assert dest < self.vertex_count
15+
self.adjacency_list[source].append(Edge(dest, weight))
16+
17+
def get_edge(self, vertex):
18+
for e in self.adjacency_list[vertex]:
19+
yield e
20+
21+
def get_vertex(self):
22+
for v in range(self.vertex_count):
23+
yield v
24+
25+
26+
def dijkstra(graph, source, dest):
27+
q = queue.PriorityQueue()
28+
parents = []
29+
distances = []
30+
start_weight = float("inf")
31+
32+
for i in graph.get_vertex():
33+
weight = start_weight
34+
if source == i:
35+
weight = 0
36+
q.put(([weight, i]))
37+
distances.append(weight)
38+
parents.append(None)
39+
40+
while not q.empty():
41+
v_tuple = q.get()
42+
v = v_tuple[1]
43+
44+
for e in graph.get_edge(v):
45+
if distances[e.vertex] > distances[v] + e.weight:
46+
distances[e.vertex] = distances[v] + e.weight
47+
parents[e.vertex] = v
48+
q.put(([distances[e.vertex], e.vertex]))
49+
50+
shortest_path = []
51+
end = dest
52+
while end is not None:
53+
shortest_path.append(end)
54+
end = parents[end]
55+
56+
shortest_path.reverse()
57+
58+
return shortest_path, distances[dest]
59+
60+
61+
def main():
62+
g = GraphWeighted(9)
63+
g.add_edge(0, 1, 4)
64+
g.add_edge(1, 7, 6)
65+
g.add_edge(1, 2, 1)
66+
g.add_edge(1, 0, 4)
67+
g.add_edge(2, 1, 1)
68+
g.add_edge(2, 3, 3)
69+
g.add_edge(3, 2, 3)
70+
g.add_edge(3, 7, 1)
71+
g.add_edge(3, 4, 2)
72+
g.add_edge(3, 5, 1)
73+
g.add_edge(4, 3, 2)
74+
g.add_edge(4, 5, 1)
75+
g.add_edge(5, 4, 1)
76+
g.add_edge(5, 3, 1)
77+
g.add_edge(5, 6, 1)
78+
g.add_edge(6, 5, 1)
79+
g.add_edge(6, 7, 2)
80+
g.add_edge(6, 8, 2)
81+
g.add_edge(7, 1, 6)
82+
g.add_edge(7, 3, 1)
83+
g.add_edge(7, 6, 2)
84+
g.add_edge(7, 8, 2)
85+
g.add_edge(8, 7, 2)
86+
g.add_edge(8, 6, 2)
87+
88+
print("Graph created")
89+
90+
shortest_path, distance = dijkstra(g, 8, 2)
91+
92+
print("shortest path:", shortest_path)
93+
print("distance:", distance)
94+
95+
96+
if __name__ == "__main__":
97+
main()

‎graphs/queue-stack.py

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
import sys
2+
import queue
3+
4+
print("queue:")
5+
6+
q = queue.Queue()
7+
8+
for i in range(15):
9+
q.put(i)
10+
11+
while not q.empty():
12+
print(q.get())
13+
14+
print("stack:")
15+
16+
s = queue.LifoQueue()
17+
18+
for i in range(15):
19+
s.put(i)
20+
21+
while not s.empty():
22+
print(s.get())
23+
24+
print("named tuple: ", sys.getsizeof(e))
25+
print("named tuple: ", sys.getsizeof(f))
26+
27+
print("tuple: ", sys.getsizeof(g))
28+
print("integer: ", sys.getsizeof(g[0]))
29+
print("integer: ", sys.getsizeof(3))
30+
print("double", sys.getsizeof(3.2987230576028765092163598235908235986))
31+
print("list:", sys.getsizeof([4, 12]))

0 commit comments

Comments
 (0)
0