Mitch's Technical Blog

Understanding Dijkstra's Algorithm

August 5, 2018
algorithms, notes, python
permalink

Aha! I finally understand Dijkstra's algorithm.

I started with some reading, watched a certain YouTube video more than once (see references below), and then I sat down to code it up starting from a blank file.

I thought my first try was brilliant. Yay! It works! Then I added another test case and...oops. It found the longest path.

I pored over the details, looking for "the bug". The code grew convoluted. Eventually I took the hint and realized I didn't have a well-defined model of the problem. No amount of debugging will fix that.

So, back to the reference material. More building of mental muscle, even though it seemed at the time like fruitless groping in the dark.

Eventually, the aha! arrived, and the way forward was clear.

Or mostly clear. While writing this post, I discovered a gap in my understanding, which led to creating a new (failing) test case, which led to a small followup aha. Writing is a discovery process!

The core idea

You have a graph with weighted edges. Suppose vertex X is on the shortest path from vertex Start to vertex End. Now imagine temporarily splitting the path in two. Start to X; X to End. If there were a shorter path from Start to X, that means there is also a shorter path from Start to End. In other words, if X is on the shortest path from Start to End, then the "subpath" to X is the shortest path to X.

Ponder that until it sinks in. Sketch it out on paper. It is the key to understanding what's going on.

The profound implication is that the algorithm can work incrementally toward the end, without having any concept of the "the whole"!

Algorithm in words

Create a scoreboard showing the cost to reach each node from the Start node. Start to Start costs 0. Everything else initially costs infinity, because it is unknown.

Begin at the Start. This is the current node.

Who are my neighbors? What is the cost to reach each of those neighbors? Is that cost less than what is currently on the scoreboard? If so, update the scoreboard to include that reduced cost. Also update it to include where you came from (in this case Start).

You've finished processing this node, so mark it as done.

Now assess: Which node to process next? Use these rules: You must not have processed it yet (otherwise you can get an infinite loop). You also cannot process the End node, which has a special status of only being considered as a neighbor. Within those constraints, pick the node which is currently closest to the start, based on the "cost" to get there.

Did you come up empty? That means you've processed all nodes and you're done!

Otherwise, repeat the process with that next current node: Who are my neighbors? What is the cost to reach each of those neighbors? Etc.

Once all nodes are processed, look on the scoreboard to retrieve the shortest path from Start to End.

References

I'm sure there is a lot of very good material out there. Here is what I found to be useful for my own learning.

The Algorithm Design Manual by Steven S. Skiena, Chapter 6, Weighted Graph Algorithms.

Note: I purchased the above directly from Springer to ensure it was the genuine article. Apparently there are some junky counterfeits out there, according to some reviews.

grokking algorithms by Aditya Y. Bhargava.

Dijkstra's Algorithm - Computerphile - YouTube

Implementation in Python

The code below runs on both Python 2.7 and 3.5+. As usual, look at doctest results for example input and output.

My implementation ended up being similar to the one in grokking algorithms. As an added bonus, it records the entire shortest path for each node, not just the immediate parent for each node. This is convenient for learning and immediate feedback, but probably Not Good for large scale performance.


MAX_COST = float('inf')

def graph1():
    out = {}
    out['A'] = {'B': 3, 'C': 1}
    out['B'] = {'A': 3, 'C': 1, 'D': 2}
    out['C'] = {'A': 1, 'B': 1, 'D': 5}
    out['D'] = {'B': 2, 'C': 5, 'E': 7}
    out['E'] = {'D': 7}

    return out

def graph2():
    out = {}
    out['A'] = {'B': 1, 'E': 8}
    out['B'] = {'A': 1, 'C': 1}
    out['C'] = {'B': 1, 'D': 1}
    out['D'] = {'C': 1, 'E': 1}
    out['E'] = {'D': 1, 'A': 8, 'F': 2}
    out['F'] = {'E': 2}

    return out

def graph3():
    out = {}
    out['A'] = {'B': 1, 'C': 1, 'D': 5}
    out['B'] = {'A': 1, 'C': 1}
    out['C'] = {'A': 1, 'B': 1}
    out['D'] = {'A': 5, 'E': 6}
    out['E'] = {'D': 6}

    return out

def graph4():
    out = {}
    out['Start'] = {'A': 2, 'End': 6}
    out['A'] = {'Start': 2, 'End': 3, 'C': 1}
    out['End'] = {'Start': 6, 'A': 3, 'C': 1}
    out['C'] = {'A': 1, 'End': 1}

    return out


def find_shortest(graph, start_node, end_node):
    """
    NOTE: Dict order is not guaranteed, so work from one value at a time
    >>> result = find_shortest(graph1(), 'A', 'D')
    >>> result['cost']
    4
    >>> result['path']
    ['A', 'C', 'B', 'D']
    >>> result = find_shortest(graph1(), 'A', 'E')
    >>> result['cost']
    11
    >>> result['path']
    ['A', 'C', 'B', 'D', 'E']
    >>> result = find_shortest(graph2(), 'A', 'F')
    >>> result['cost']
    6
    >>> result['path']
    ['A', 'B', 'C', 'D', 'E', 'F']
    >>> result = find_shortest(graph3(), 'A', 'E')
    >>> result['cost']
    11
    >>> result['path']
    ['A', 'D', 'E']
    >>> result = find_shortest(graph4(), 'Start', 'End')
    >>> result['cost']
    4
    >>> result['path']
    ['Start', 'A', 'C', 'End']
    """
    costs = init_trip_cost(graph, start_node)
    completed = []

    node = start_node

    while node is not None: 
        # Update cost to reach each neighbor
        for neighbor in graph[node].keys():
            cost = costs[node]['cost'] + graph[node][neighbor]
            if cost < costs[neighbor]['cost']:
                costs[neighbor]['cost'] = cost
                costs[neighbor]['path'] = costs[node]['path'] + [neighbor]

        # We're done with this node
        completed.append(node)

        # Here lies the core of the algorithm.
        # Find the closest node which has not yet been processed.
        # Ingenious because it enables course correction! A previously
        # "promising" course might have gotten suddenly expensive,
        # which now makes a previously de-prioritized path the front-runner.
        # The logic is tied to the provable assertion that any
        # node which is the shortest distance from the start must
        # also be on the path to the end. In other words, the driving
        # idea is to continuously determine the shortest node from the
        # start, until we have processed every node.
        smallest = MAX_COST
        node = None

        candidates = [n for n in costs.keys()
                      if n != end_node
                      and not n in completed]

        for n in candidates: 
            ncost = costs[n]['cost']
            if ncost < smallest:
                smallest = ncost
                node = n

    return costs[end_node]


def init_trip_cost(graph, start_node):
    out = {}
    for k in graph.keys():
        out[k] = {'cost': MAX_COST, 'path': []}

    out[start_node]['cost'] = 0
    out[start_node]['path'] = [start_node]

    return out


if __name__ == '__main__':
    from doctest import testmod
    testmod(verbose=True)


Contact: hello at escapefromsql.net