Djiksta’s Algorithm

You are given a start vetex $s$, and it finds the shortest path from $s$ to every other vertex in the graph, including your desired destination $t$.

Shortest Path does not necessarily mean it is the fastest path; it means that the path has the least number of segments (edges).

Steps for Djikstra’s:

  1. Find the cheapest node starting from the source/start vertex.
  2. Update the costs of the neighbors of this node.
  3. Repeat until you’ve done this for every node in the graph.
  4. Calculate the final path

What is a Cycle?

You start at a node, travel around, and end up at the same node.

In an undirected graph, if two nodes are connected, that means they point to each other, so they have a cycle!

Calculating the shortest paths

  1. If you have an unweighted graph, you use breadth-first search.
  2. If you have a weighted graph, you use Dijkstra’s algorithm.