Dijkstra All Pairs S P Algorithm

The Dijkstra All Pairs Shortest Path (APSP) Algorithm is an extension of the classic Dijkstra's Shortest Path algorithm, which is designed to find the shortest path between a single source and all other vertices in a graph. The APSP version of the algorithm aims to find the shortest path between every possible pair of vertices in a given graph. This is particularly useful in situations where it is necessary to determine the most efficient routes between multiple locations, such as in transportation, computer networking, and optimization problems.

Dijkstra's APSP algorithm works by iteratively applying the single-source Dijkstra's algorithm for each vertex in the graph, treating it as the starting point. In each iteration, the algorithm maintains a set of unvisited vertices, and a tentative distance value for each vertex. It initializes the distance to the starting vertex as zero, and the distance to all other vertices as infinity. The algorithm then repeatedly selects the unvisited vertex with the smallest tentative distance, updates the tentative distances of its neighbors, and marks the vertex as visited. After all vertices have been visited, the algorithm has computed the shortest path from the starting vertex to all other vertices. By repeating this process for all vertices in the graph, the shortest path between every pair of vertices is obtained. While this approach can be computationally expensive for large graphs, it has the advantage of simplicity and the ability to handle graphs with both positive and negative edge weights, as long as there are no negative cycles.

 package org.gs.digraph
 
/** Solves for all pairs shortest path from a source where edge weights are non-negative
  *
  * @constructor creates a new DijkstraAllPairsSP with an edge weighted digraph
  * @param g acyclic digraph, edges have direction and weight
  * @see [[https://algs4.cs.princeton.edu/44sp/DijkstraAllPairsSP.java.html]]
  * @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
  */
class DijkstraAllPairsSP(g: EdgeWeightedDigraph) {
  private val all = for (v <- 0 until g.numV) yield new DijkstraSP(g, v)
 
  /** returns path from source to t if it exists */
  def path(s: Int, t: Int): Option[List[DirectedEdge]] = all(s) pathTo(t)
 
  /** returns length of shortest path from source to t */
  def dist(s: Int, t: Int): Double = all(s) distTo(t)
 
  /** returns if there is a path from source to t */
  def hasPath(s: Int, t: Int): Boolean = dist(s, t) < Double.PositiveInfinity
}

Dijkstra All Pairs S P Algorithm

LANGUAGE:

DARK MODE:

PROGRAMMING LANGUAGES:

Python

Java

Javascript

C#

C++

C

Ruby

Scala

MATLAB

Kotlin

Rust

R

Go

	package org.gs.digraph

	/** Solves for all pairs shortest path from a source where edge weights are non-negative
	*
	* @constructor creates a new DijkstraAllPairsSP with an edge weighted digraph
	* @param g acyclic digraph, edges have direction and weight
	* @see [[https://algs4.cs.princeton.edu/44sp/DijkstraAllPairsSP.java.html]]
	* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
	*/
	class DijkstraAllPairsSP(g: EdgeWeightedDigraph) {
	private val all = for (v <- 0 until g.numV) yield new DijkstraSP(g, v)

	/** returns path from source to t if it exists */
	def path(s: Int, t: Int): Option[List[DirectedEdge]] = all(s) pathTo(t)

	/** returns length of shortest path from source to t */
	def dist(s: Int, t: Int): Double = all(s) distTo(t)

	/** returns if there is a path from source to t */
	def hasPath(s: Int, t: Int): Boolean = dist(s, t) < Double.PositiveInfinity
	}