Teaching Kids Programming – Introduction to Dijkstra Single Source Shortest Path Graph Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two-dimensional list of integers edges which represents a directed, weighted graph. Each element in edges contains [u, v, w] meaning that there is an edge from node u to node v which costs positive weight w. You are also given integers start and end.

Return the cost of the shortest path from start to end. If there is no path between the two nodes, return -1.

Constraints
1 ≤ n ≤ 100,000 where n is the length of edges
Example 1
Input

1 2 3 4 5

edges = [     [0, 1, 3],     [1, 2, 2],     [0, 2, 9] ]

edges = [
    [0, 1, 3],
    [1, 2, 2],
    [0, 2, 9]
]

start = 0
end = 2
Output
5
Explanation
We can go 0 to 1 for cost of 3 and then 1 to 2 for cost of 2.

Dijkstra Single Source Shortest Path Graph Algorithm

The Dijkstra Algorithm is the most famous Single Source Shortest Path (SSSP) Algorithm for a Weighted Graph with no negative weight. Dijkstra is optimal as the time complexity is . It is fast as it makes an assumption that the weights of the edges are positive.

The Dijkstra algorithm consists of two steps (and repeat it): Update the Estimates and then Pick the next vertex with the smallest cost in the unexplored set of vertices.

1. Update the Estimates: Dijkstra updates the shortest distance from the current vertex to all the neighbour vertices that it connects to. Initially, the cost to all the vertices in the Graph except the source is infinity.
2. Pick the next vertex from unexplored set of vertices. Once Dijkstra explores a vertex, it has the shortest path to it and assumes there is no shorter path by adding more edges with positive weights

Here is the Dijkstra algorithm in Python. Dijkstra has many variants and below is the classic one that is implemented using Priority Queue (or heap). Dijkstra is complete as one the queue is empty, it has all the shortest paths from the source to all other vertices. Uniform Cost Search (UCS) is a variant of Dijkstra and UCS is incomplete.

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:
    def solve(self, edges, s, e):
        G = defaultdict(list)
        N = 0
        for a, b, w in edges:
            G[a] += [(b, w)]
            N = max(N, a, b)
        N += 1
        
        def dijkstra(s, e):
            q = [(0, s)]
            d = defaultdict(lambda: inf)
            seen = set()
            while q:
                c, v = heappop(q)
                if v in seen:
                    continue
                seen.add(v)
                for x, w in G[v]:
                    if c + w < d[x]:
                        d[x] = c + w
                        heappush(q, (c + w, x))
            return d[e] if d[e] < inf else -1

class Solution:
    def solve(self, edges, s, e):
        G = defaultdict(list)
        N = 0
        for a, b, w in edges:
            G[a] += [(b, w)]
            N = max(N, a, b)
        N += 1
        
        def dijkstra(s, e):
            q = [(0, s)]
            d = defaultdict(lambda: inf)
            seen = set()
            while q:
                c, v = heappop(q)
                if v in seen:
                    continue
                seen.add(v)
                for x, w in G[v]:
                    if c + w < d[x]:
                        d[x] = c + w
                        heappush(q, (c + w, x))
            return d[e] if d[e] < inf else -1

Unlike Dijkstra, BFS (Breadth First Search) Algorithm is based on queue (First In First Out) and can only work in unweighted graphs (or graphs with equal weights). The time complexity for BFS is as in the worst case, the BFS needs to explore all the edges and vertices. BFS traverses the graph in level by level order. And Dijkstra can be categorized as “Best First Search” as it uses a heap or priority queue to extract the current “best” aka minimal cost from the queue.

The Floyd Warshal, on the other hand, is a multi source short path algorithm that runs in a much higher complexity e.g. time and space.

Shortest Path Algorithms

• Teaching Kids Programming – Distance Between Bus Stops (Floyd Warshal Shortest Path in Simple Undirected Weighted Regular Graph)
• Teaching Kids Programming – Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph
• Teaching Kids Programming – A Light Talk on Breadth First Search, Uniform Cost Search and Dijkstra Shortest Path Graph Algorithms
• Teaching Kids Programming – Introduction to Dijkstra Single Source Shortest Path Graph Algorithm
• Teaching Kids Programming – Single Source Shortest Path Algorithm in a Directed Unweighted Graph using Breadth First Search
• Teaching Kids Programming – Floyd Warshal Multi-source/All Pairs Shortest Path Algorithm (Sum of Costs in a Directed Unweighted Graph)
• Teaching Kids Programming – Uniform Cost Search Algorithm to Solve Single-Source Shortest Path in a Graph
• Teaching Kids Programming – Shortest Path Algorithms by Iterative Deepening Search (IDS), Depth First Search (DFS) or Breadth First Search (BFS) on Undirected Graphs
• Teaching Kids Programming – Finding the Network Delay Time via Floyd-Warshall Shortest Path Algorithm
• Teaching Kids Programming – Distance Between Bus Stops (Shortest Distance in Simple Undirected Weighted Regular Graph)

–EOF (The Ultimate Computing & Technology Blog) —