Finding Shortest Path with Dijkstra's Algorithm

Welcome back, everyone!

What do YOU need to know about Dijkstra's Algortihm?

• Process used to find the shortest path in a graph from a start node to other nodes
• The fastest, single start, shortest path algorith for directed and undirected graphs with unbouded, non-negative edge weights
• Tough to spell: D-I-J-K-S-T-R-A
• If you thought the info here is garbo you can check out this link (which isn't a virus): האלגוריתם של דיקסטרה

How to Use Dijkstra's Algorithm

The pseudocode is provided below and its elegance will leave you quivering.

The algorithm uses a priority queue to keep track of nodes and edges. It makes sure not to visit the same node twice.

You'll begin with a graph that looks like this:

And finessing the algorithm you can find the shortest path from a start node to all other nodes. Let's say we wanted to commence at node A.

You'll eventually cook something up that looks like this (small feast):

Reminders (emotional)

• professor sees god

Acknowledgements

This presentation would not have been possible without Devoy.