Dijkstra's Algorithm

Babu lives in a certain village A, and having been in the same village all his life, he longs to travel to the villages reachable from his. Due to time and work constraint, he can only get to one village at a time, and he has therefore to plan accordingly. His idea is to sort the distances from his village to each of the other villages in increasing order, and to visit the villages in that order. So his first task is to get the shortest distances from A to every other village.

A map of Babu's village and all the other villages is as shown below. As can be seen, Babu, the guy drawn as a red stick figure, is currently at his own village, village A. There are roads interconnecting some of the villages, and you can see the length of the roads in the drawing.




Assume that Babu at this point doesn't know yet what's the actual shortest distance from A to every other village. He knows of course that the distance from A to A is 0, and mark it down as shown in the map below. And he puts the distance to every other village as infinity. He will update the value as he goes along.




Now, Babu thinks about all the cities that can be directly reached from A. That's B, G and F, circled as shown in the picture below:



He notes the distances from A to B, G and F, and  he list down the places in his notebook - his next-to-visit list -, sorted by distance:




To keep things manageable and his head clear , he keeps as well a logbook containing the list of villages, and for each whether it has been visited, the current shortest distance to it, and the preceding village to route through to reach the destination village.




G, being the nearest - at a distance of 4 from A - , he goes there.




There, he notes the yet-to-visit cities that can be reached directly from G - B, C, D, E, F. He notes down the distances to the cities via G, marking it on the map, overriding the previous values of infinities.




He updates his logbook as well:


He places B, C, D, E, F in his next-to-be-visited list, maintaining the sorted order in the list, and he goes home. The new list is as shown below, with B in the lead, it being the nearest next to visit.




So next he visited B, and he mark on the map the next villages to be visited. From B, there's only one directly reachable village that's yet to be visited - C. But the distance to C via B is 9, not less than that distance already recorded for C, so no change in the logbook. The preceding village for C remains as G. And C is already in the next-to-visit list; so no change whatsoever.

With B, now out from the next-to-visit list, we now have as follows:



So Babu goes to D next.



From D, the villages directly reachable are C and E. However, distance to C through D would be 6+9 = 15, greater than the 9 already recorded. And E through D would be 6 + 5 = 11, way more than the 7 recorded. So the distances to C ad E should not change in Babu's logbook.



Next trip for Babu will be to E, as indicated in his next-to-visit list:




So he goes to E, and from E, he notes that the next to visit village is F. But the distance to F through E is 11, more than the recorded distance for F. So nothing much to do here.

By this point, Babu's logbook looks as follows:



Only F and C left.

Finishing it all off, eventually Babu's logbook looks as follows:



The distances shown in the logbook now will be the final distances, the shortest distance from village A to every other village.

The algorithmic approach adopted by Babu is referred to these days as Dijkstra's Algorithm. In Python, we can have it implemented as shown below. I used the heap data structure in the code, to maintain a sorted list of unvisited nodes. Heap and Heapsort will be in a different post/

# function parameters: the adjacency matrix, the list of nodes (villages) and 
# the starting node 
def dijkstra(adjmat, unvisited_queue, start):
# in adjmat, -1 entry at (i,j) indicates there is no edge between node i and j

    # Set the distance for the start node to zero
    start['dist'] = 0

    heapq = Heap('dist') 
    # Put all nodes into the heap; the heap will maintain a sorted list
    heapq.InsertAll(unvisited_queue)

    # Repeat until the heap is empty
    while heapq.Size() > 0:
        # Pops the node with the smallest distance
        current = heapq.Pop()
        # Get the index for that node
        currIndex = current['index']
        # Get the visit status for the node to True
        current['visited'] = True
     
        # Get list of nodes adjacent from the current node     
        adjacent = [unvisited_queue[i] for i in range(len(unvisited_queue))
                        if unvisited_queue[i]['index'] != currIndex and
                        adjmat[unvisited_queue[i]['index']][currIndex] >= 0]

        # Repeat for each adjacent node   
        for next in adjacent:
            # if the adjacent node has already been visited, skip
            if next['visited'] == True:
                continue

            # get the index for the adjacent node
            nextIndex = next['index']
            # compute distance to adjacent node via current node
            new_dist = current['dist'] + adjmat[currIndex][nextIndex]

            # if new distance is less, update the one stored in the adj node         
            if new_dist < next['dist']:
                next['dist'] = new_dist
                # the current node now precedes the adj node
                next['preceding'] = currIndex
                # we have to make sure that the information is updated in the heap
                heapq.Change(next)

    return nodes

Array Representation of a Complete Binary Tree

The binary tree is ubiquitous in Computer Science, being especially useful for storing data in a way that allows for efficient access and operations. The question to be addressed in this post is: how to implement a binary tree?  

Like a List ADT, a binary tree may be implemented as a linked list or as an array, the more intuitively straightforward being the linked list implementation.

Pythonically, one can imagine a crude implementation based on Python dict:

child0 = { 'data': 4,

                 'child0': None,

                 'child1': None }

child1 = { 'data': 5,

                 'child0': None,

                 'child1': None }

root = { 'data': 3, 

               'child0': child0,

               'child1': child1 }

or with C/C++ struct, as follows

struct Node {

          int data;

          Node * child0;

          Node * child1;

   };

But if we can put it all in a straightforward array, like as follows, it would be better:

There wouldn't be any need to store pointers or references in each node. It means less memory consumed...

The tricky part in putting it all into an array is the indexing... Consider the following binary tree:

Suppose we lay the nodes out in the array in a breadth-first manner, as follows:

Note that 4 and 5 are the children of node 3, 6 and 7 that of  4.  Can you see any pattern here? 

Node 4 is in index 2(0) + 1 = 2.

Node 5 in index 2(0) + 2 = 2..

Node 6 is stored in index 2(1) + 1 = 3.

Node 7 in index 2(1) + 2 = 4.

Hmm...

Let's try with a full binary tree:

Laying it out linearly in a breadth-first manner, we have:

And it does seem that the formula work..

Given a node at index n, its first child will be at 2n + 1, and the second one at 2n + 2.

So far, it works with a complete binary tree.  Will it work with one that is incomplete?

And how do we get the parent of a node? Can you work it out?

Radix Sort

In a previous post, I talked about Counting Sort, an O(N) sorting algorithm that is not comparison-based. If you have read the post (or you already know about Counting Sort), you may have realized that Counting Sort can be so fast simply because it deals with very simple, limited form of input - single-digit integers.

The question that naturally arise then is: can we extend Counting Sort to bigger numbers, say  a list comprising of integers of arbitrary size?

Let's try to work things out... Say we have just 2 numbers...

Can we apply Counting Sort to these numbers?? Counting Sort is only for single digit... but what if we apply it to one number position at a time, maybe start from the least significant position (the rightmost side)...

Applying Counting Sort to that 1st position (from the right, place value = 1), we get:

Then apply Counting Sort again, this time to position 2 (place value 10):

No change, of course, since it's the value 2 in that positions for both numbers. Going on to the most significant figure (the leftmost number, or place value 100), there is no change in the order, since 1 is less than 3. So the final sorted order is: 121  323.

Hmm.. things seem to look good...

Let's try with a bit more complex example:

Applying Counting Sort to the least significant position, we obtain:

Moving on the next position, there's no change in the ordering: 2 - 2 - 9. So we move on to the most significant position.

But here's a subtlety: 121 and 323 each has 3 digits, while 99 has only 2. Hence the most significant positions for 121 and 323 are not the same as that for 99. A solution to this is simple, however - simply assume a zero in from of 99, as you can see above.

Hence, applying Counting Sort to the most significant bit, we obtain:

It works, right? Well, this is Radix Sort, a sorting algorithm that applies Counting Sort to sort a sequence of integers. To do the digit by digit sorting, we can code as follows:

def radixSort(alist):
    max = max(alist)
    placevalue = 1
    while max > placevalue:
        alist = countingSort(alist,placevalue)
        placevalue *= 10
    return alist

In the code above, we first compute max, the maximum number in the input list, alist. max, being the biggest number, will of course have the maximum number of digits. We start with the least significant position, at placevalue = 1,  and multiply placevalue by 10 at every iteration. The loop ends when placevalue is more than max.

The function countingSort itself needs a slight modification from the one shown in the post on Counting Sort. We need to pass in place value as a parameter, and use it to sort numbers based on the digits at the corresponding position.

def countingSort(arr, placevalue):
    n = len(arr)

    output = [0] * n
    count = [0] * 10

    for i in range(n):
        num = (arr[i]//placevalue)
        index = num%10
        count[index] += 1

    for i in range(9):
        count[i+1] += count[i]
     
    for i in range(9, 0, -1):
        count[i] = count[i-1]
    count[0] = 0
 
 
    for i in range(len(arr)):
        num = (arr[i]//placevalue)
        index = num%10
        output[ count[index] ] = arr[i]
        count[index] += 1

    return output

Counting Sort

Suppose we are given a list of numbers each between 0 and 9 inclusive. In other words, its all single-digit non-negative integers. For example, we have the list: 3, 9, 7, 6, 6, 4, 8. The sorted output is: 3, 4, 6, 6, 7, 8, 9.
How do we sort this? We can use something like quicksort, yes, with a complexity of O(N log N). But can we do better? To put it more precisely, since the best you can get with any comparison-based sorting is O(N log N)  - see for example the explanation at https://www.geeksforgeeks.org/lower-bound-on-comparison-based-sorting-algorithms/ -, can we something non-comparison based for this relatively very simple data sequence?

Consider the sorted output again: 3, 4, 6, 6, 7, 8, 9.
Of course we know that 3 comes before 4, 4 before 6 and so on. The main problem it seems is to get the number of items that come before each of the number in the input sequence. For example, there is zero items before 3, a single item before 4, two items before 6, four before 7 and so on and so on..    If we know then cumulative number of each digit before a particular digit x, then we can compute the position of x in the output list.

To compute these cumulative numbers, we can first count the frequency of all numbers from 0 to 9, storing those values in an array as shown below:

You can see in the picture that number 3 occurs once, 9 once, '6' twice and so on. To compute the cumulative count for number 3, we need to count the total number of occurrence for the numbers from 0 to 2. In general, for a number x > 0, we need the sum of the frequency of the numbers from 0 to x-1. The easiest way to do this is via 2 loops. The first loop compute as follows:

    for i in range(9):

        count[i+1] += count[i]

The outcome is as shown below:

The second loop performs a shift, so that the cumulative count for a digit x does not include the number x itself. 

It might sound (and look) complicated, but all we have to do is the following:

    for i in range(9, 0, -1):
        count[i] = count[i-1]
    count[0] = 0

Once we have the array of accumulated counts - a count array -, the numbers you have in there will be the indices for the numbers in the input list. For each number, x, in the input list, look up the the value at index x in count. The value you get is the index for x in the output array. 

    for i in range(len(arr)):
        index = arr[i]
        sorted[ count[index] ] = arr[i]
        count[index] += 1

Note a certain subtlety: the code above increments the value in count, - count[index]++ - after reading it. This will ensure that if you get the same x value later in the input list, it will be in a different location from the earlier x.

The overall code looks as follows:

def countingSort(arr):

   # initialize
    n = len(arr)
    sorted = [0] * n
    count = [0] * 10

   # count frequency for each number
    for i in range(n):
        index = arr[i]
        count[index] += 1

   # accumulate the count
    for i in range(9):
        count[i+1] += count[i]
    
    # do the shift   
    for i in range(9, 0, -1):
        count[i] = count[i-1]
    count[0] = 0   
   
   # compute the final sorted list 
    for i in range(len(arr)):
        index = arr[i]
        sorted[ count[index] ] = arr[i]
        count[index] += 1

    return sorted

Quicksort

Given a list to be sorted, such as the one below

the main idea in quicksort is to take one guy to be the 'pivot', say the leftmost guy.. (give him a cap)

and then to put bigger guys to his right, and smaller ones to his left, like as follows:

Then, you need to recursively apply the logic, to both the right and the left sublist:

Hence, at the high level, the code is simple, shown below here in Python:

def quickSort(alist, first, last):  
    if first < last:
       splitpoint = partition(alist, first, last)
       quickSort(alist,first,splitpoint-1)
       quickSort(alist,splitpoint+1,last)

where first is the first index, and last the last one. partition performs the positioning, and returns the final position of the pivot.

The tricky part is in doing the partitioning efficiently, without having to create new lists to store the left and right partitions, that is to do it all in-place. The main idea in partition is as follows:

Suppose pivot is the first guy below (red). Initialize a left pointer that starts at the second guy, and a right pointer that starts at the last.



Pythonically,
   pivotvalue = alist[first]

where alist is the name of the list, and first is the first index.

Further

   left = first+1
   right= last

Do as follows:
While the guy pointed to by left is less than pivot, increment left by one (move it one step to the right). Similarly, while the guy pointed to by right is more than pivot, decrement right by one.  Eventually, left and right will be at the positions below:



In code:
   while not done:
       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1


The outer while loop above continues till right is less than left:

       if rightmark < leftmark:
           done = True

If right is still not less than left, we have to do a swap.  Swap the guys at left and right positions.



Continue the main while loop above, and you get...


Now swap right and pivot:


Partitioning is done - smaller guys to the left of pivot, and bigger ones to the right.

The overall code for partition is as follows:

def partition(alist,first,last):
   pivot = alist[first]

   left = first+1
   right = last

   done = False
   while not done:
       while left <= right and alist[left] <= pivot:
           left = left + 1

       while alist[right] >= pivot and right >= left:
           right = right -1

       if right < left:
           done = True
       else:
           swap(alist, left, right)

   swap(alist, first, right)
   return right