Design Graph With Shortest Path Calculator
Problem
Build a directed weighted graph with n nodes 0 … n−1. Each edge [from, to, cost] goes one way with a positive cost. Implement a Graph class with three operations:
Graph(n, edges) initializes the graph. addEdge([from, to, cost]) inserts a new directed edge. shortestPath(node1, node2) returns the minimum total cost of any path from node1 to node2, or −1 if none exists.
Graph(4, [[0,2,5],[0,1,2],[1,2,1],[3,0,3]]); shortestPath(3, 2)6import heapq
class Graph:
def __init__(self, n, edges):
self.n = n
self.adj = [[] for _ in range(n)] # adjacency list
for f, t, c in edges:
self.adj[f].append((t, c))
def addEdge(self, edge):
f, t, c = edge
self.adj[f].append((t, c)) # one new directed edge
def shortestPath(self, node1, node2):
dist = [float('inf')] * self.n # best cost known so far
dist[node1] = 0
pq = [(0, node1)] # min-heap of (cost, node)
while pq:
d, u = heapq.heappop(pq) # cheapest frontier node
if u == node2:
return d # target settled: answer
if d > dist[u]:
continue # stale heap entry, skip
for v, w in self.adj[u]: # relax each outgoing edge
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return -1 # node2 unreachableclass Graph {
constructor(n, edges) {
this.n = n;
this.adj = Array.from({ length: n }, () => []); // adjacency list
for (const [f, t, c] of edges) this.adj[f].push([t, c]);
}
addEdge(edge) {
const [f, t, c] = edge;
this.adj[f].push([t, c]); // one new directed edge
}
shortestPath(node1, node2) {
const dist = new Array(this.n).fill(Infinity); // best cost so far
dist[node1] = 0;
const pq = new MinHeap(); // (cost, node) min-heap
pq.push([0, node1]);
while (pq.size()) {
const [d, u] = pq.pop(); // cheapest frontier node
if (u === node2) return d; // target settled
if (d > dist[u]) continue; // stale entry, skip
for (const [v, w] of this.adj[u]) { // relax outgoing edges
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push([dist[v], v]);
}
}
}
return -1; // unreachable
}
}class Graph {
private List<int[]>[] adj;
private int n;
public Graph(int n, int[][] edges) {
this.n = n;
adj = new List[n]; // adjacency list
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] e : edges) adj[e[0]].add(new int[]{e[1], e[2]});
}
public void addEdge(int[] edge) {
adj[edge[0]].add(new int[]{edge[1], edge[2]}); // new directed edge
}
public int shortestPath(int node1, int node2) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE); // best cost so far
dist[node1] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, node1}); // (cost, node)
while (!pq.isEmpty()) {
int[] top = pq.poll();
int d = top[0], u = top[1]; // cheapest frontier
if (u == node2) return d; // target settled
if (d > dist[u]) continue; // stale entry, skip
for (int[] e : adj[u]) { // relax outgoing
int v = e[0], w = e[1];
if (d + w < dist[v]) {
dist[v] = d + w;
pq.offer(new int[]{dist[v], v});
}
}
}
return -1; // unreachable
}
}class Graph {
int n;
vector<vector<pair<int,int>>> adj; // adjacency list
public:
Graph(int n, vector<vector<int>>& edges) : n(n), adj(n) {
for (auto& e : edges) adj[e[0]].push_back({e[1], e[2]});
}
void addEdge(vector<int> edge) {
adj[edge[0]].push_back({edge[1], edge[2]}); // new directed edge
}
int shortestPath(int node1, int node2) {
vector<long> dist(n, LONG_MAX); // best cost so far
dist[node1] = 0;
priority_queue<pair<long,int>, vector<pair<long,int>>,
greater<>> pq; // (cost, node)
pq.push({0, node1});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop(); // cheapest frontier
if (u == node2) return (int)d; // target settled
if (d > dist[u]) continue; // stale entry, skip
for (auto& [v, w] : adj[u]) { // relax outgoing
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return -1; // unreachable
}
};Explanation
The graph itself is just an adjacency list: for each node we keep a list of (neighbor, cost) pairs. The constructor fills it from the initial edges, and addEdge appends a single new directed edge — both are O(1) amortized. All the real work lives in shortestPath.
Because every edge cost is positive, the right tool is Dijkstra's algorithm. We keep a dist array of the best cost found to each node (everything starts at ∞ except the source, which is 0) and a min-heap of (cost, node) entries. Repeatedly we pop the cheapest frontier node — the first time a node leaves the heap, its distance is final.
When we pop node u with cost d, we relax each outgoing edge u → v of weight w: if d + w beats the recorded dist[v], we lower it and push the improved entry. We may push the same node more than once, so a stale pop (where d > dist[u]) is simply skipped.
The moment we pop the target node2, that popped cost is the shortest distance, so we return it immediately. If the heap empties without ever reaching node2, no path exists and we return −1.
In Example 1, querying shortestPath(3, 2) settles 3 (cost 0), then 0 (cost 3), then 1 (cost 5) — beating the direct 0 → 2 edge — and finally pops 2 at cost 6, the answer.