Parallel all-pairs shortest path algorithm: Difference between revisions

Revision as of 19:57, 12 October 2024

Revision as of 01:12, 14 October 2024

Line 10:

Let <math>G=(V,E,w)</math> be a directed Graph with the set of nodes <math>V</math> and the set of edges <math>E\subseteq V\times V</math>. Each edge <math>e \in E</math> has a weight <math>w(e)</math> assigned. The goal of the all-pair-shortest-paths problem is to find the shortest path between '''all''' pairs of nodes of the graph. For this path to be unique it is required that the graph does not contain cycles with a negative weight.

In the remainder of the article it is assumed that the graph is represented using an [[adjacency matrix]]. We expect the output of the algorithm to be a distancematrix <math>D</math>. In <math>D</math>, every entry <math>d-d_{i,j}</math> is the weight of the shortest path in <math>G</math> from node <math>i</math> to node <math>j</math>.

The [[Floyd algorithm]] presented later can handle negative edge weights, whereas the [[Dijkstra algorithm]] requires all edges to have a positive weight.