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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

Insert the start node into a priority queue with cost 0.
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.

If the goal is unreachable, return failure.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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.

Problem#

Examples#

Example 1#

Solution#

Method 1 – Uniform Cost Search (Priority Queue)#

Intuition#

Approach#

Code#

Complexity#