Hello, this is #day_29, I'm going to talk about Dijkstra's shortest path algorithm

## Definition of Dijkstra's shortest path algorithm

dijkstra's shortest path is an algorithm created by **Dr. Edsger Dijkstra** for calculating the shortest path between vertices in a weighted graph (*types of graph*)

## Example of a weighted graph

## Dijkstra's shortest path applications

- Road networks
- Electricity lines
- Google maps
- Social networking apps
- Flighting agenda
- Ip routing more details

## Dijkstra's shortest path implementation in python

If you are not familiar with Python check this series by @aatmaj

```
def dijkstraShortestPathAlgo(nodes, edges, source_indedx = 0):
"""
code from
=> [https://www.youtube.com/watch?v=VnTlW572Sc4]
"""
path_lengths = {v:float('inf') for v in nodes}
path_lengths[source_index] = 0
adjacent_nodes = {v:{} for v in nodes}
for (u, v), w_uv in edges.items():
adjacent_nodes[u][v] = w_uv
adjacent_nodes[v][u] = w_uv
temporary_nodes = [v for v in nodes]
while len(temporary_nodes) > 0:
upper_bounds = {v: path_lengths[v] for v in temporary_nodes}
u = min(upper_bounds, key=upper_bounds.get)
temporary_nodes.remove(u)
for v, w_uv in adjacent_nodes[u].items():
path_lengths[v] = min(path_lengths[v], path_lengths[u] + w_uv)
return path_lengths
```

## References & useful resources

- https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
- https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/
- https://www.youtube.com/watch?v=smHnz2RHJBY

Happy coding!!

## Top comments (0)