Single source

Shortest path from one source to all vertices.

Single source

Dijkstra's algorithm finds shortest paths from a single source node to all other nodes in a graph. It requires non-negative weights.

The output is a distance array: dist[i] is the shortest distance from the source to i. The algorithm fails if there are negative edges.

Adjacency list

The graph is represented as a list of neighbors for each node. Each element is a (neighbor, weight) pair; for example graph[0] = [(1, 4), (2, 1)].

This representation saves space in sparse graphs and lets Dijkstra run efficiently.

Exercise init_graph function

Write init_graph(). Return the adjacency list. Print it with print(init_graph()).

Show example solution

def init_graph():
    # Return adjacency list
    return [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], []]
print(init_graph())

Test yourself

Which case does Dijkstra not support?
- Negative weights
- Non-negative weights
- Zero weights
- Integer weights
Show answer

Negative weights — Dijkstra does not support negative weights.

Edge weight

graph[0] = [(1, ____)]

Show answer

graph[0] = [(1, 4)]

Single source: match the terms

graph[0]

[(1,4),(2,1)]
graph[1]

[(3,1)]
graph[2]

[(1,2),(3,5)]
graph[3]

[]

Next lesson: Priority queue

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies