<aside> <img src="/icons/help-alternate_gray.svg" alt="/icons/help-alternate_gray.svg" width="40px" /> As noted before, most of the topics covered in this lecture are pretty much recap of what we covered in COE428. For reference: COE428 - Algorithms and Data Structures.

</aside>

Shortest Path

We define the shortest path as the minimum weight path from a vertex $s$ to another vertex $t$ in a directed graph, if such a path exists.

Figure 3.1 A directed graph with weighted edges.

Figure 3.1 A directed graph with weighted edges.

As you can see, each edge has a weight (or cost) to them. Suppose we choose vertex $A$ as our starting point, then the shortest paths available are:

Figure 3.2 Shortest paths from vertex $A$.

Figure 3.2 Shortest paths from vertex $A$.

If you calculate the weight from the source vertex $A$ to every other vertex, you will get the minimum edge weight possible.

You may noticed that the shortest paths are not unique, meaning there can be more than one shortest path, nonetheless all of them should still provide the same answer with the shortest path.

  1. Dijkstra’s algorithm
  2. Bellman-Ford algorithm

<aside> 💡 Note that Bellman-Ford’s algorithm is not considered as a greedy algorithm. It takes a dynamic programming approach to implement the algorithm, but nonetheless, we will include in this section.

</aside>

Both algorithms solve the shortest path problem by repeatedly using edge relaxation. The process of relaxing an edge is to check if its worth traversing through the edge $\langle u,v \rangle$ which would improve the shortest path from source vertex $s$ to some vertex $t$.