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

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 $tex_8bbedbf8fd07930da323e2ffab149714 Teaching Kids Programming - Introduction to Dijkstra Single Source Shortest Path Graph Algorithm algorithms Dijkstra Shortest Path Graph Algorithm python teaching kids programming youtube video$. 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
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 $tex_633059c67c35025d7a6a07fec0ca6663 Teaching Kids Programming - Introduction to Dijkstra Single Source Shortest Path Graph Algorithm algorithms Dijkstra Shortest Path Graph Algorithm python teaching kids programming youtube video$ 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. $tex_7a76d6674dd1fcfdd41f44c3fcd0f07a Teaching Kids Programming - Introduction to Dijkstra Single Source Shortest Path Graph Algorithm algorithms Dijkstra Shortest Path Graph Algorithm python teaching kids programming youtube video$ time and $tex_84dc4634ea26f37367902b093c57dc5c Teaching Kids Programming - Introduction to Dijkstra Single Source Shortest Path Graph Algorithm algorithms Dijkstra Shortest Path Graph Algorithm python teaching kids programming youtube video$ space.

GD Star Rating