Weighted vs Unweighted Graphs: What is the Difference?
Learn the difference between weighted and unweighted graphs, and which shortest-path algorithm fits each for this interview question.
Expected Interview Answer
A weighted graph attaches a numeric cost or value to each edge, such as distance or price, while an unweighted graph only records that a connection exists with no associated cost, meaning every edge is effectively treated as cost one.
In an unweighted graph, the shortest path is simply the path with the fewest edges, which is exactly what breadth-first search finds efficiently in O(V + E) time. In a weighted graph, the “shortest” path means the path with the lowest total edge cost, which requires algorithms like Dijkstra for non-negative weights or Bellman-Ford when negative weights are possible, since BFS no longer gives correct results. Weighted graphs model real costs like road distance, network latency, or transaction amounts, while unweighted graphs are appropriate when only connectivity matters, like a simple friendship network. The representation itself barely changes — an adjacency list just stores a weight alongside each neighbor — but the choice of traversal algorithm changes completely.
- Unweighted graphs: BFS finds shortest path in O(V + E)
- Weighted graphs: Dijkstra/Bellman-Ford find lowest-cost path
- Weighted edges model real-world costs like distance or price
- Same storage structure, different algorithm requirements
AI Mentor Explanation
An unweighted rivalry graph just marks whether two teams have played each other at all, so the “closest” rival is simply whoever they faced most recently with the fewest connecting matches in between. A weighted version instead labels each link with something like margin of victory or ranking-points swing, so finding the “strongest” chain of rivalries means adding up those numbers rather than just counting links. In the unweighted graph, a simple queue-based scan finds the shortest chain of connections between any two teams. In the weighted graph, you need an algorithm that always expands the cheapest-so-far path first, because a chain with fewer matches can still cost more in total points than a longer chain of easy wins.
Step-by-Step Explanation
Step 1
Identify if edges carry a cost
Weighted graphs store a numeric value per edge (distance, price, time); unweighted graphs treat every edge as cost one.
Step 2
Pick BFS for unweighted shortest path
BFS explores level by level, guaranteeing the fewest-edge path in O(V + E).
Step 3
Pick Dijkstra for weighted shortest path
Dijkstra always expands the currently cheapest known path first, using a min-heap, for non-negative weights.
Step 4
Pick Bellman-Ford if negative weights exist
Bellman-Ford handles negative edge weights and detects negative cycles, at O(V * E) cost.
What Interviewer Expects
- Define weighted vs unweighted clearly with a real example each
- State that BFS solves unweighted shortest path, not weighted
- Name Dijkstra as the standard weighted shortest-path algorithm
- Know Dijkstra fails with negative weights and Bellman-Ford is needed instead
Common Mistakes
- Using BFS on a weighted graph and assuming it still finds the cheapest path
- Forgetting Dijkstra requires non-negative edge weights
- Treating “shortest path” as always meaning fewest edges, even in weighted graphs
- Not mentioning Bellman-Ford as the fallback for negative weights
Best Answer (HR Friendly)
“An unweighted graph only cares whether two things are connected, so the shortest path just means the fewest steps. A weighted graph adds a real cost to each connection, like distance or price, so I need a different algorithm, like Dijkstra, to find the cheapest path instead of just the shortest one.”
Code Example
from collections import deque
import heapq
def bfs_shortest_path(graph, start, goal):
queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = queue.popleft()
if node == goal:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
def dijkstra(graph, start):
dist = {start: 0}
pq = [(0, start)]
while pq:
d, node = heapq.heappop(pq)
if d > dist.get(node, float("inf")):
continue
for neighbor, weight in graph[node]:
new_dist = d + weight
if new_dist < dist.get(neighbor, float("inf")):
dist[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return distFollow-up Questions
- Why does BFS fail to find the correct shortest path on a weighted graph?
- What happens to Dijkstra if the graph has negative edge weights?
- How would you modify Dijkstra to reconstruct the actual shortest path, not just its cost?
- When would you choose Bellman-Ford over Dijkstra?
MCQ Practice
1. Which algorithm correctly finds the shortest path in an unweighted graph?
BFS explores nodes in order of edge count from the source, which is exactly the shortest path in an unweighted graph.
2. What is required for Dijkstra to produce correct results?
Dijkstra assumes distances only increase as you extend a path, which breaks with negative edge weights.
3. Which algorithm should be used on a weighted graph that may contain negative edge weights?
Bellman-Ford correctly handles negative weights and can also detect negative-weight cycles.
Flash Cards
What does an edge weight represent? — A numeric cost, such as distance, time, or price, associated with traversing that edge.
Which algorithm finds shortest paths in an unweighted graph? — BFS, in O(V + E) time.
Which algorithm finds shortest paths in a weighted graph with non-negative weights? — Dijkstra algorithm, using a min-heap.
What algorithm handles negative edge weights? — Bellman-Ford, which also detects negative-weight cycles.