In [ ]:
%%HTML
<style>
.container { width:100% }
</style>
In [ ]:
%run Heap-Array.ipynb
In [ ]:
def shortest_path(source, Edges):
Distance = { source: 0 }
Visited = { source } # this set is only needed for visualization
Fringe = [] # priority queue, organized as array based heap
insert(Fringe, (0, source))
while Fringe != []:
display(heapToDot(Fringe))
d, u = remove(Fringe)
display(toDot(source, u, Edges, Fringe, Distance, Visited))
print('_' * 80)
for v, l in Edges[u]:
dv = Distance.get(v, None)
if dv == None or d + l < dv:
if dv != None:
elevate(Fringe, v, d + l)
else:
insert(Fringe, (d + l, v))
Distance[v] = d + l
Visited |= { u }
display(toDot(source, None, Edges, Fringe, Distance, Visited))
return Distance
In [ ]:
import graphviz as gv
The function $\texttt{toDot}(\texttt{source}, \texttt{Edges}, \texttt{Fringe}, \texttt{Distance}, \texttt{Visited})$ takes a graph that is represented by
its Edges, a set of nodes Fringe, and a dictionary Distance that has the distance of a node from the node source, and set Visited of nodes that have already been visited.
In [ ]:
def toDot(source, p, Edges, Fringe, Distance, Visited):
V = set()
for x in Edges.keys():
V.add(x)
dot = gv.Digraph(node_attr={'shape': 'record', 'style': 'rounded'})
dot.attr(rankdir='LR', size='8,5')
for x in V:
if x == source:
dot.node(str(x), color='blue', shape='doublecircle')
else:
d = str(Distance.get(x, ''))
if x == p:
dot.node(str(x), label='{' + str(x) + '|' + d + '}', color='magenta')
elif x in Distance and (Distance[x], x) in Fringe:
dot.node(str(x), label='{' + str(x) + '|' + d + '}', color='red')
elif x in Visited:
dot.node(str(x), label='{' + str(x) + '|' + d + '}', color='blue')
else:
dot.node(str(x), label='{' + str(x) + '|' + d + '}')
for u in V:
for v, l in Edges[u]:
dot.edge(str(u), str(v), label=str(l))
return dot
In [ ]:
a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')
e = Node('e')
f = Node('f')
g = Node('g')
h = Node('h')
In [ ]:
Edges = { a: [ (c, 2), (b, 9)],
b: [(d, 1)],
c: [(e, 5), (g, 3)],
d: [(f, 2), (e, 4)],
e: [(f, 1), (b, 2)],
f: [(h, 5)],
g: [(e, 1)],
h: []
}
In [ ]:
sp = shortest_path(a, Edges)
sp
Four persons, Alice, Britney, Charly and Daniel have to cross a tunnel. The tunnel is so narrow, that at most two persons can cross it together. In order to cross the tunnel, a torch is needed. Together, they only have a single torch.
What is the fastest plan to cross the tunnel?
In [ ]:
All = frozenset({ 'Alice', 'Britney', 'Charly', 'Daniel', 'Torch' })
Time = { 'Alice': 1, 'Britney': 2, 'Charly': 4, 'Daniel': 5, 'Torch': 0 }
The function $\texttt{power}(M)$ defined below computes the power list of the set $M$, i.e. we have: $$ \texttt{power}(M) = 2^M = \bigl\{A \mid A \subseteq M \bigr\} $$
In [ ]:
def power(M):
if M == set():
return { frozenset() }
else:
C = set(M) # C is a copy of M as we don't want to change the set M
x = C.pop() # pop removes the element x from the set C
P1 = power(C)
P2 = { A | {x} for A in P1 }
return P1 | P2
If $B$ is a set of persons, then $\texttt{duration}(B)$ is the time that this group needs to cross the tunnel.
$B$ also contains 'Torch'.
In [ ]:
NodeDict = { S: Node(S) for S in power(All) }
In [ ]:
def duration(B):
return max(Time[x] for x in B)
$\texttt{left_right}(S)$ describes a crossing of the tunnel from left to right.
In [ ]:
def left_right(S):
return [(NodeDict[S - B], duration(B)) for B in power(S) if 'Torch' in B and 2 <= len(B) <= 3]
$\texttt{right_left}(S)$ describes a crossing of the tunnel from right to left.
In [ ]:
def right_left(S):
return [(NodeDict[S | B], duration(B)) for B in power(All - S) if 'Torch' in B and 2 <= len(B) <= 3]
In [ ]:
Edges = { Node(S): left_right(S) + right_left(S) for S in power(All) }
len(Edges)
The function shortest_path is Dikstra's algorithm. It returns both a dictionary containing the parents and a dictionary
with the distances.
In [ ]:
def shortest_path(source, Edges):
Distance = { source: 0 }
Parent = {}
Fringe = []
insert(Fringe, (0, source) )
while Fringe != []:
d, u = remove(Fringe)
for v, l in Edges[u]:
dv = Distance.get(v, None)
if dv == None or d + l < dv:
if dv != None:
elevate(Fringe, v, d + l)
else:
insert(Fringe, (d + l, v))
Distance[v] = d + l
Parent[v] = u
return Parent, Distance
In [ ]:
start = Node(frozenset(All))
In [ ]:
Parent, Distance = shortest_path(start, Edges)
Let us see whether the goal was reachable and how long it takes to reach the goal.
In [ ]:
goal = NodeDict[frozenset()]
Distance[goal]
Given to nodes source and goal and a dictionary containing the parent of every node, the function
find_path returns the path from source to goal.
In [ ]:
def find_path(source, goal, Parent):
p = Parent.get(goal)
if p == None:
return [source]
return find_path(source, p, Parent) + [goal]
In [ ]:
Path = [x.mValue for x in find_path(NodeDict[frozenset(All)], NodeDict[frozenset()], Parent)]
In [ ]:
def print_path():
total = 0
print("_" * 81);
for i in range(len(Path)):
Left = set(Path[i])
Right = set(All) - set(Left)
if Left == set() or Right == set():
print(Left, " " * 25, Right)
else:
print(Left, " " * 30, Right)
print("_" * 81);
if i < len(Path) - 1:
if "Torch" in Path[i]:
Diff = set(Path[i]) - set(Path[i+1])
time = duration(Diff)
total += time
print(" " * 20, ">>> ", Diff, ':', time, " >>>")
else:
Diff = set(Path[i+1]) - set(Path[i])
time = duration(Diff)
total += time
print(" " * 20, "<<< ", Diff, ':', time, " <<<")
print("_" * 81)
print('Total time:', total, 'minutes.')
In [ ]:
print_path()
In [ ]: