Uniform Cost Search

Problem

Given a weighted graph and a start and goal node, find the lowest-cost path from start to goal using Uniform Cost Search (UCS). UCS is equivalent to Dijkstra's algorithm for graphs with non-negative weights.

Examples

Example 1

graph LR;
A(1) -->|3| B(2)
A -->|1| C(3)
B -->|3| D(4)
C -->|1| D
D -->|3| G(5)
C -->|2| G
S(0) -->|1| A
S -->|12| G

Input:
n = 6
adj = [
  [(1,1),(5,12)],   # 0: S -> A(1), G(12)
  [(2,3),(3,1)],    # 1: A -> B(3), C(1)
  [(4,3)],          # 2: B -> D(3)
  [(4,1),(5,2)],    # 3: C -> D(1), G(2)
  [(5,3)],          # 4: D -> G(3)
  []                # 5: G
]
start, goal = 0, 5
Output: 4
Explanation: Graph as shown above. UCS finds the lowest-cost path from 0 to 5, which is this one: 0 → 1 → 3 → 5, expanding nodes in order of cumulative cost.

Here is how the search will look like:

graph TD;
  S(0) ---|1| A(1)
  S(0) ---|12| G(5)

  A(1) ---|1| B(2)
  A(1) ---|3| C(3)

  B ---|3| D(4) ---|3| G2(5)
  C ---|1| D2(4) ---|3| G3(5)
  C ---|2| G4(5)

Solution

Method 1 – Uniform Cost Search (Priority Queue)

Intuition

UCS always expands the node with the lowest cumulative cost so far, guaranteeing the optimal path in graphs with non-negative weights. It uses a priority queue to manage the frontier.

Approach

1. Insert the start node into a priority queue with cost 0.
2. While the queue is not empty:

• Remove the node with the lowest cost.
• If it is the goal, return the path and cost.
• Otherwise, add all neighbors to the queue with updated cumulative costs.

3. If the goal is unreachable, return failure.

Code

C++

#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
  int ucs(int n, vector<vector<pair<int,int>>>& adj, int start, int goal) {
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
      auto [cost, u] = pq.top(); pq.pop();
      if (u == goal) return cost;
      if (cost > dist[u]) continue;
      for (auto& [v, w] : adj[u]) {
        if (dist[v] > cost + w) {
          dist[v] = cost + w;
          pq.push({dist[v], v});
        }
      }
    }
    return -1;
  }
};

Java

class Solution {
  public int ucs(int n, List<List<int[]>> adj, int start, int goal) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    dist[start] = 0;
    pq.offer(new int[]{0, start});
    while (!pq.isEmpty()) {
      int[] cur = pq.poll();
      int cost = cur[0], u = cur[1];
      if (u == goal) return cost;
      if (cost > dist[u]) continue;
      for (int[] edge : adj.get(u)) {
        int v = edge[0], w = edge[1];
        if (dist[v] > cost + w) {
          dist[v] = cost + w;
          pq.offer(new int[]{dist[v], v});
        }
      }
    }
    return -1;
  }
}

Python

class Solution:
  def ucs(self, n: int, adj: list[list[tuple[int,int]]], start: int, goal: int) -> int:
    import heapq
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]
    while pq:
      cost, u = heapq.heappop(pq)
      if u == goal:
        return cost
      if cost > dist[u]:
        continue
      for v, w in adj[u]:
        if dist[v] > cost + w:
          dist[v] = cost + w
          heapq.heappush(pq, (dist[v], v))
    return -1

Complexity

• ⏰ Time complexity: O((V + E) log V), where V is the number of nodes and E is the number of edges (using a priority queue).
• 🧺 Space complexity: O(V + E), for the adjacency list and distance array.