summary - All Pairs Shortest Path

📲
All Pairs Shortest Path
course Algorithmics

last review @April 24, 2023

mastery rookie

assignment

progress not started

Weight

Files

date

due date

notes

days left



All Pairs Shortest Path
The All Pairs Shortest Path algorithm is used to determine the shortest path between
all pairs of vertices in a given weighted graph. It is an extension of the Dijkstra's and
Floyd Warshall's algorithm. This algorithm can be used to solve various graph
problems such as finding the diameter of a graph, detecting negative cycles in a
graph, and solving the Travelling Salesman Problem.


Example
Consider the following weighted graph:


1
(A)---->(B)
| /|\\
4| / | \\ 2
| / | \\
v / v v




All Pairs Shortest Path 1