4-in-1 Priority First Search in Python: BFS, DFS, Prim’s, and Dijkstra’s algorithms

I first learned in my college years in Sedgwick’s algorithm book to see Prim’s minimum spanning tree algorithm and Dijkstra’s single source shortest path algorithm as two applications of the same priority first search algorithm. Moreover, it is also easy to see that breadth first search and (a slightly different version of) depth first search can also be implemented using priority first search. This semester I am teaching data structures. It surprises me that even today it’s difficult to find a sample program that combines these four algorithms to illustrate their similarity. This article on Prim’s algorithm briefly mentions bfs and dfs. This article is closest to what I am looking for. I find it more comfortable to read it using the lynx text browser.

So I have written this small program pfs.py . For the theoretical aspects, readers can google each algorithm to find many excellent explanations of how and why they work. Here in this article I will just explain my code.

To use my program one has to install three python packages first: pip3 install pqdict pydot networkx The input data has to be formatted as a graphviz dot file and therefore can also be rendered as svg/png/jpg graphic files for illustration purposes. See t01.dot and t02.dot for examples.

The program is run like this :

python3 pfs.py -a dijk -0 E t02.dot
python3 pfs.py -a prim -0 G t02.dot

The -a option specifies the algorithm (one of bfs, dfs, prim, and dijk). The -0 option specifies the name of the starting node/vertex (let’s call it v0). The program will print nodes in the order they are visited. (See below for definition.) The ancestors, starting from the parent all the way to the starting node v0, will be printed along with each visited node.

Here goes the succinct version of the pseudo code:

PQ.insert(v0)
while (not PQ.is_empty()) {
    v = PQ.remove();
    v.status = 'visited';
    for w in v.neighbors {
        if (not defined(w.status)) {
	    ++vid;
	}
	new_priority = ###priority computation###
        if (not defined(w.status)) {
            w.status = 'fringe';
            w.parent = v;
            w.priority = new_priority
            PQ.insert(w)
        } elseif (w.status == 'fringe' and \
	          algorithm in ['prim', 'dijk']) {
            if (new_priority < w.priority) {
                w.parent = v;
                w.priority = new_priority
		PQ.heapify(w)
            }
        }
    }
}

During the graph traversal, the status of each node changes from “unseen” to “fringe” to “visited”. Fringe nodes are stored in a priority queue PQ and processed one by one to become visited in the order according to their priority. These four algorithms differ mainly in their priority computation:

bfs:   vid
dfs:  -vid
prim: vw.weight
dijk: v.priority + vw.weight

where vid (vertex ID) is a counter incremented for each newly-seen (previously unseen) node and vw.weight is the weight of the edge connecting v and w. Moreover the priority of a fringe node and its parent pointer may need to be updated when it is seen from a different visited node.

To facilitate tracing, the code (1) sorts the neighbors of the node being visited according to their names and (2) prints the ancestors of each visited node. Obviously one could omit these two pieces of code if optimal time O((E+V)*log(V)) is desired. Also one would use integer indices in place of node names if it is to be implemented in a programming language without associative array (dictionary) support.

I find it convenient to store information about each node directly in the node data structure of the networkx package. To make it clearly distinctive from any built-in properties, I prefix the names of my properties with “#”.

Hopefully the actual code is almost as concise as the pseudo code. I love searching for and making use of Free/Libre/Open Source packages to make my program both concise and functional :-)