TIW: Dijkstra

Shortest path problems using Dijkstra are actually very easy to write. There is a fixed format and you just need to fill in the blanks. The format:

  1. Optional pre-computation to create the graph;
  2. Make a set of pairs, insert initial state;
  3. While the set is not empty, pop the best one;
  4. If it is the destination, return the distance;
  5. If we have been to this node, continue to the next, otherwise mark this node as visited;
  6. Insert all the neighbors into the set.

In fact, Dijkstra is such a no-brainer that I sometimes write Dijkstra where BFS suffices, even though it gives an extra log(n) factor to the runtime.

Let’s make up a toy problem and see how it works. Say, a 2D maze search. Input: a matrix of characters, walk from any ‘S’ to any ‘T’, using only ‘.’ as path. Return the length of the shortest path. For example

..S
.XX
..T

Will return 6.

Here’s the code:

 

bool inboard(int x, int y, int m, int n) {
    return x >= 0 && x < m && y >= 0 && y < n;
}
int mazeSearch(vector<string>& maze) {
    int m = maze.size(), n = maze[0].size();
    set<pair<int, pair<int, int> > > st;
    vector<vector<bool> > vis(m, vector<bool>(n));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (maze[i][j] == 'S')
                st.insert(make_pair(0, make_pair(i, j)));  // insert all initial states with distance 0
    vector<vector<int> > dir{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    while (!st.empty()) {
        auto sm = *st.begin();  // smallest item in the set, closest unvisited state from source
        st.erase(sm);  // popping the heap
        int r = sm.second.first, c = sm.second.second;
        if (vis[r])
            continue;
        vis[r] = true;
        if (maze[r] == 'T')
            return sm.first;  // found shortest path
        for (auto d : dir) {
            int nr = r+d[0], nc = c+d[1];
            if (inboard(nr, nc, m, n) && (maze[nr][nc] == '.' || maze[nr][nc] == 'T'))
                st.insert(make_pair(sm.first+1, make_pair(nr, nc)));  // next states with 1 distance farther from source
        }
    }
    return -1;  // no path found
}

The main tricks here are to use a set as a heap and a pair to denote a state. A few benefits of this trick:

  1. Set has log(n) insert, remove and maximum/minimum query, ideal for Dijkstra.
  2. Set has built-in duplicate removal, potentially saving a lot of extra work.
  3. Pair has default comparator as mentioned in STL#1, so we do not have to write our own.

The alternative is to use std::priority_queue<>. I cannot think of any reason why using priority queue would be superior. There are a few reasons I do not prefer them: the name is longer to type, does not have duplicate removal, requires extra work to get a min-heap (since it is by default a max-heap), and I don’t remember the syntax and would have to Google every time. Getting a min-heap or max-heap out of std::set<> is trivial: just change *st.begin() to *st.rbegin(). the first item from the end is the largest item.

Of course this problem only requires BFS.  You can modify the above code by changing the set to a vector and changing the while to a for loop, shown in the BFS blog post earlier. But this is just an example to demonstrate the structure of a Dijkstra implementation.

Unfortunately there is no problem that needs Dijkstra on Leetcode; although you could certainly use it to replace some BFS problems. Then maybe I’ll slightly go over A* using the same code structure just for fun. If you really understand the above, it is trivial to modify it for similar problems.

A* by augmenting Dijkstra

A* is just Dijkstra with a “postpone” function that estimates a lower bound for the distance of a node to destination. When the postpone function is 0, we get exactly Dijkstra. Think of it this way: you are a college student with a homework assigned, and have to submit before it is due. Given that you don’t know the due date, but it is at least tomorrow night. Are you going to do it now? Of course no. But given you only know the due date is before next Sunday, it might actually be tonight, so you have to do it now. The same idea applies to A*: if we know this path definitely takes at least 10 steps, we can safely postpone walking it after we have tried all paths that could possibly take 9 steps.

To implement A* with the above code: instead of putting in the distance from source at the first item of each pair, put the distance from source plus the estimated lower bound distance from destination.

Once again I don’t have a good problem, and it is also not that common, so I’ll skip the details. The actual function form highly depends on the problem. In some cases it might even be impossible or useless to calculate a lower bound. So A* is definitely not the one ring to rule it all, but it’s still good to know.

Leave a Reply

Your email address will not be published. Required fields are marked *