One way to speed up Dijkstra’s algorithm is to keep the list of pending nodes in sorted order.
computer science
Description
1). Pseudo-Code to Python (20 Marks)
One way to speed up Dijkstra’s algorithm
is to keep the list of pending nodes in sorted order. If we were to apply a sort every time,
though, this could get prohibitive because the best sorts are O(n lg n). An alternative uses a Heap. The pseudo-code for the functions below
implement insert and serve for a Heap. Insert
adds a new node to the list in the appropriate place. Serve
removes the lowest node from the list and reorders the list. A heap is O (lg n) which is much faster than
a sort.
In the following two sections, each entry
in the list consists of a tuple of the form (name, value). Implement each function from the pseudo-code
given. Put both the insert and serve
functions in a single python file called ‘heap.py”.
1a). Heap Insert (10)
insert (list, node, value)
Creates a new tuple (node, list) and uses
the following algorithm to put that node into the list in heap order
I.
Create the tuple
II.
Add the tuple to the end of
the list
III.
Child = length of list - 1
IV.
Parent = Child // 2
V.
While Child ≠ Parent and
list[Child]’s cost < list[Parent] cost
A.
Swap list[Child] with
list[Parent]
B.
Child = Parent
C.
Parent = Child // 2
Example Run:
def
test(): heap = [] insert (heap, "A", 10) print (heap) insert (heap, "B", 15) insert (heap, "C", 5) print (heap) insert (heap, "D", 18) insert (heap, "E", 2) print (heap)
Output:
>>> test()
[('A', 10)]
[('C', 5), ('A', 10), ('B', 15)]
[('E', 2), ('C', 5), ('A', 10),
('D', 18), ('B', 15)]
1b). Heap Serve (10) serve (list)
Returns the first element in the list.
I.
Answer = list[0]
II.
Last = Pop Last Element in
list
III.
list[0] = Last
IV.
Parent = 0
V.
While True
A.
Left = Parent * 2 + 1
B.
Right = Parent * 2 + 2
C.
If Left >= length of list
1. Return Answer
Else if Right >= length of list
1. Swap list[Parent] and list[Left]
2. Parent = Left
Else if list[Left]’s cost <
list[Right]’s Cost
1. Swap list[Parent] and list[Left]
2. Parent = Left
Else
1. Swap list[Parent] and list[Right]
2.
Parent = Right
