Shortest Path Problems

Tags:

Given a weighted graph G Given a weighted graph G (V,E), =(V,E), and a source vertex s, find the minimum weighted path from s to every other vertex in G

Unweighted graph

If the graph is unweighted, we can solve this problem using Bread First Search.

Weighted Graph

For Weighted Graph, we solve this problem use Dijkstra’s algorithm.

shortest path between all pairs of vertices

Given G(V,E), find a shortest path between all pairs of vertices.

Solutions: (brute -force) Solve Single Source Shortest Path for each vertex as source.  There are more efficient ways of solving this problem (e.g., Floyd problem (e.g., Floyd -Warshall algorithm).

To be continued