Algorithms for the shortest path

Dijkstra's algorithm

Given a non-negative weighted graph G(V, E), Dijkstra's algorithm is to find the shortest path from a source node s to a target node $t$.

As shown in Figure 1, Dijkstra's algorithm picks the unvisited node with the shortest distance to s and update the distance (if smaller) through it to its unvisited neighbors. Because of non-negative weights, adding a edge can never make the path shorter.

Figure 1: Pick the unvisited (yellow) node v with the shortest distance to s. Credit: Keith's lecture slide 02 of CS 161.

The pseudo code of Dijkstra's algorithm is as follows:

My implementation in C++ that is the solution of Leetcode 743 is as follows:

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<vector<int>> graph(N, vector<int>(N, -1));
        for (const auto& edge : times) {
            graph[edge[0]-1][edge[1]-1] = edge[2];
        }
        vector<int> dist(N, INT_MAX);
        dist[K-1] = 0;
        auto compare = [](const pair<int, int>&a, const pair<int, int>&b) {
            return a.first > b.first;  
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>,
                       decltype(compare)> queue(compare);
        queue.emplace(0, K-1);
        while (!queue.empty()) {
            int node_id = queue.top().second;
            queue.pop();
            for (int i = 0; i < N; ++i) {
                if (graph[node_id][i] > -1 && 
                    dist[i] > dist[node_id] + graph[node_id][i]) {
                    dist[i] = dist[node_id] + graph[node_id][i];
                    queue.emplace(dist[i], i);
                }
            }
        }
        int result = *max_element(dist.begin(), dist.end());
        return result < INT_MAX ? result : -1;
    }
};

Note that the C++ container priority_queue does not support the function of updating the distance of an existing node in the queue. Instead of updating the weight in-place, we simply push another copy of the node but with the updated weight. Thinking for a momentum, one can realize that the priority queue implementation of Dijkstra's still works if the priority queue contains multiple copies of the same node with different weights in the queue since the copies of the node with higher weights will never be used.

In some cases, one can even push the node into the priority queue when dist[i] > dist[node_id] + graph[node_id][i]. For example, the python implementation of Leetcode 787 is as follows:

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, p in flights:
            graph[u].append((p, v))
        heap = [(0, src, k+1)]
        while heap:
            result, i, l = heapq.heappop(heap)
            if i == dst:
                return result
            if l > 0:
                for p, j in graph[i]:
                    heapq.heappush(heap, (result+p, j, l-1))
        return -1

The above python implementation is correct but TLE. The implementation, in which we skip pushes that are certainly unnecessary, is as follows:

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, p in flights:
            graph[u].append((p, v))
        heap = [(0, src, k+1)]
        stops = [-1] * n
        while heap:
            result, i, l = heapq.heappop(heap)
            if i == dst:
                return result
            if stops[i] >= l:
                continue
            stops[i] = l
            if l > 0:
                for p, j in graph[i]:
                    heapq.heappush(heap, (result+p, j, l-1))
        return -1

0-1 BFS

In a special case in which all the edge weights are either 0 or 1, we can simplify Dijkstra's algorithm by using a deque instead of priority_queue: If the edge is zero (one), we push the node at the start (end) of the deque. The following is my C++ implementation that is the solution of Leetcode 1368:

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        deque<pair<int, int>> queue({{0, 0}});
        dist[0][0] = 0;
        const int dirs[4][2] = {{0, 1},{0, -1}, {1, 0}, {-1, 0}};
        while (!queue.empty()) {
            int x = queue.front().first;
            int y = queue.front().second;
            queue.pop_front();
            if (x == m-1 && y == n-1) {
                return dist[x][y];
            }
            for (int i = 1; i < 5; ++i) {
                int k = x + dirs[i-1][0];
                int l = y + dirs[i-1][1];
                if (k >= 0 && k < m && l >= 0 && l < n &&
                    dist[k][l] > dist[x][y] + (i != grid[x][y])) {
                    dist[k][l] = dist[x][y] + (i != grid[x][y]);
                    if (i == grid[x][y]) {
                        queue.emplace_front(k, l);
                    } else {
                        queue.emplace_back(k, l);
                    }    
                }
            }
        }
        return -1;
    }
};

A* search

A* search improves Dijkstra's algorithm by modifying the weight of a node u in priority_queue from d(s, u) to d(s, u) + h(u). h(u) is the heuristic function that estimates the shortest distance from u to t. It should not be larger than the actual distance between u and t (admissible). A common heuristic function on 2D grid is Manhattan distance.

Here is my C++ implementation of A* search that is the solution of Leetcode 1263:

struct State {
    int bx;
    int by;
    int px;
    int py;
    int moves;
    int estimate;
    bool operator < (const State& other) const {
        return estimate > other.estimate;
    }
};

class Solution {
public:
    int minPushBox(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int bx, by, px, py, tx, ty, moves = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                switch(grid[i][j]) {
                    case 'S':
                        px = i; py = j;
                        break;
                    case 'B':
                        bx = i; by = j;
                        break;
                    case 'T':
                        tx = i; ty = j;
                        break;
                }
            }
        }
        int estimate = heuristic(bx, by, tx, ty);
        vector<vector<int>> dist(m * n, vector<int>(m * n, INT_MAX));
        dist[bx * n + by][px * n + py] = estimate;
        priority_queue<State> queue;
        queue.push({bx, by, px, py, moves, estimate});
        const int actions[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        while (!queue.empty()) {
            const State state = move(queue.top());
            queue.pop();
            if (state.bx == tx && state.by == ty) {
                return state.moves;
            }
            for (const auto& action : actions) {
                px = state.px + action[0];
                py = state.py + action[1];
                if (!is_valid(px, py, m, n, grid)) {
                    continue;
                }
                bx = state.bx;
                by = state.by;
                moves = state.moves;
                if (px == state.bx && py == state.by) {
                    bx += action[0];
                    by += action[1];
                    ++moves;
                }
                if (!is_valid(bx, by, m, n, grid)) {
                    continue;
                }
                estimate = heuristic(bx, by, tx, ty) + moves;
                if (dist[bx * n + by][px * n + py] > estimate) {
                    dist[bx * n + by][px * n + py] = estimate;
                    queue.push({bx, by, px, py, moves, estimate});
                }
            }
        }
        return -1;
    }
    
    inline bool is_valid(int i, int j, const int m, const int n,
                         const vector<vector<char>>& grid) {
        return i >= 0 && i < m && j >=0 && j < n && grid[i][j] != '#';
    }
    
    inline int heuristic(int i, int j, const int tx, const int ty) {
        return abs(i - tx) + abs(j - ty);
    }
};

This problem can also be solved by 0/1 BFS as

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        start = [0] * 5
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "S":
                    start[0: 2] = [i, j]
                elif grid[i][j] == "B":
                    start[2: 4] = [i, j]
        start = tuple(start)
        visited = set([start])
        queue = collections.deque([start])
        def is_valid(x, y):
            return 0 <= x < m and 0 <= y < n and grid[x][y] != "#"
        while queue:
            xp, yp, xb, yb, result = queue.popleft()
            if grid[xb][yb] == "T":
                return result
            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nxp, nyp = xp + dx, yp + dy
                nxb, nyb, new_result = xb, yb, result 
                if nxp == xb and nyp == yb:
                    nxb, nyb, new_result = xb + dx, yb + dy, result + 1
                if is_valid(nxp, nyp) and is_valid(nxb, nyb) and (nxp, nyp, nxb, nyb) not in visited:
                    visited.add((nxp, nyp, nxb, nyb))
                    if new_result == result:
                        queue.appendleft((nxp, nyp, nxb, nyb, result))
                    else:
                        queue.append((nxp, nyp, nxb, nyb, new_result))
        return -1

Search This Blog

Life with Physics