Abstract / Summary

Design a graph that supports adding edges and finding the shortest path between two nodes.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 65% (100k+ submissions).

Typical patterns to solve this problem:

• Design
• Graph Theory
• Heap (Priority Queue)
• Shortest Path

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Graph class builds a directed weighted graph from a list of edges and offers a method to compute the minimum cost path between two vertices. Construction stores adjacency information and edge costs separately, while the path-finding routine combines a breadth-first search style traversal with a priority queue to realize Dijkstra’s algorithm. The implementation includes several early-exit checks and data-structure choices that keep the search efficient even on sparse graphs.

Graph Construction

The constructor receives the vertex count n and a collection of edges. It initializes three containers:

self.nodes = defaultdict(list)
self.costs = defaultdict(list)
self.have  = set()

self.nodes maps a source vertex to a list of destination vertices, self.costs stores the parallel list of edge weights, and self.have records every vertex that appears in any edge. The loop iterates over the supplied edges and delegates insertion to addEdge:

for e in edges:
    self.addEdge(e)

Adding an Edge

addEdge extracts the source, destination, and weight from the edge tuple and updates the adjacency structures:

a, b, cost = edge
self.nodes[a].append(b)
self.costs[a].append(cost)
self.have.add(a)
self.have.add(b)

By using defaultdict(list), the code avoids explicit existence checks before appending, and the have set provides O(1) membership tests for later validation.

Shortest Path Computation

The shortestPath method determines the least-cost route from node1 to node2. It begins with two guard clauses that handle trivial and impossible scenarios:

if node1 == node2:
    return 0
if node1 not in self.have or node2 not in self.have:
    return -1

The first clause returns zero when the source and destination coincide, while the second returns -1 if either endpoint never appears in any edge, effectively signaling an unreachable target.

Priority Queue Initialization

A min-heap is created to store candidate paths, each represented as a tuple (cumulative_cost, vertex):

todo = [(0, node1)]
seen = set()

The seen set records vertices whose shortest distance has already been finalized, preventing redundant processing.

Main Exploration Loop

The algorithm repeatedly extracts the lowest-cost entry from the heap:

while todo:
    cost, node = heappop(todo)

If the extracted vertex matches the destination, the accumulated cost is returned immediately:

if node == node2:
    return cost

Vertices already processed are skipped:

if node in seen:
    continue
seen.add(node)

When a vertex lacks outgoing edges, the loop simply proceeds to the next heap entry:

if node not in self.nodes:
    continue

Otherwise, the code iterates over parallel adjacency and cost lists using zip, pushing new candidates onto the heap for each unvisited neighbor:

for nextnode, nextcost in zip(self.nodes[node], self.costs[node]):
    if nextnode not in seen:
        heappush(todo, (cost + nextcost, nextnode))

If the heap empties without reaching the target, -1 is returned to indicate that no path exists.

Edge Cases Handled

The implementation explicitly addresses several boundary conditions:

• Identical source and destination vertices return a zero cost without entering the search.
• Queries involving vertices absent from any edge are rejected early with -1.
• Vertices that have no outgoing edges are safely ignored during expansion, preventing key errors.
• The seen set eliminates cycles and repeated processing, ensuring that loops in the graph do not cause infinite traversal.
• The final -1 return covers the situation where the graph is disconnected or the destination is unreachable from the source.

Performance Optimizations

Several design choices contribute to efficient execution:

• Storing adjacency and cost information in parallel lists enables fast iteration without constructing intermediate edge objects.
• The defaultdict eliminates conditional checks for missing keys during edge insertion, reducing overhead.
• The have set provides constant-time existence checks for the early validation of source and destination vertices.
• Using a binary heap (heapq) ensures that each extraction and insertion operates in logarithmic time relative to the number of pending candidates.
• Early termination upon reaching the target vertex avoids unnecessary exploration of the remaining search space.
• The seen set prevents revisiting vertices whose shortest distance has already been determined, which is essential for Dijkstra’s correctness and reduces the number of heap operations.

Collectively, these techniques allow the shortestPath method to scale well with graph size, particularly when the graph is sparse and the number of explored vertices is limited by the priority-driven search order.

Imagine you have a big map filled with little treasure chests scattered across different islands. Some islands are connected by bridges, and each bridge has a specific number of tiny pebbles you have to pay to cross it.

The first part of the code is like building this map. It keeps a notebook that lists every island and which other islands you can reach from there. It also remembers how many pebbles each bridge costs so you never get lost.

When it comes time to find the best way to get from one island to another, the code starts a little game of follow the path. It makes a special list of all the places you can go next, always picking the path that costs the fewest pebbles first. Because it wants to be very smart, it keeps a separate pile of places it has already visited so it does not walk in circles.

Every time it reaches a new island, it looks at all the bridges connected to it. It adds up the pebbles used so far and compares the new path to any others it has seen. It keeps doing this, jumping from one island to the next using the cheapest bridges, until it finally lands on the island that holds the treasure you are looking for. If it checks every possible bridge and still cannot find a way to get to your destination, it concludes that there is simply no way to travel between those two spots.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java	C++				Python	TS
	WalkCCC	Java	C++				Python
	leetcode.ca	Java	C++		C#	Go	Python	TS
	Progiez	Java	C++				Python
github	charles-wangkai	Java
	everthis			JS
	fsq		C++
	varunu28	Java
	wisdompeak		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality