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

**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.

- 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.
- 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

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

1314 words

**Last Post**: Teaching Kids Programming – Distance Between Bus Stops (Shortest Path in Simple Undirected Weighted Regular Graph) **Next Post**: Teaching Kids Programming – A Light Talk on Breadth First Search, Uniform Cost Search and Dijkstra Shortest Path Graph Algorithms

Source: Internet