scalation
API
Generated with
scalation/scalation/scalation.database/scalation.database.graph_pm/ShortestPath

ShortestPath

scalation.database.graph_pm.ShortestPath
See theShortestPath companion object
class ShortestPath(c: MatrixD, s: Int)

The ShortestPath class is used to solve shortest path problems for graphs stored in matrices. It solves the Single-Source Shortest Path (SSSP) problem for directed graphs. The ShortestPath companion object is used to form a matrix from a Graph.

The edge cost/distance (must be non-negative) is stored in a dense matrix. Dijkstra's Algorithm is used: @see en.wikipedia.org/wiki/Dijkstra%27s_algorithm

To extend to multi-digraphs, each multi-edge between a pair vertices has it own edge weight. Take the minimum when forming the corresponding matrix.

Value parameters

c

the cost/distance matrix, where a value of zero implies no connection. If the actual distance is zero, use a very small number instead.

s

the single-source vertex

Attributes

See also
Companion
object
Graph
Supertypes
class Object
trait Matchable
class Any

Members list

Type members

Classlikes

case class Item(id: Int, dd: Double) extends Ordered[Item]

The Item inner case class has two fields, vertex id and distance from vertex s (the source) as well as a compare method based on distance.

The Item inner case class has two fields, vertex id and distance from vertex s (the source) as well as a compare method based on distance.

Value parameters

dd

the vertex's distance from vertex s

id

the id of the vertex

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait Ordered[Item]
trait Comparable[Item]
class Object
trait Matchable
class Any
Show all

Value members

Concrete methods

def spath(): (VectorD, VectorI)

Determine the shortest path from vertex s to each vertex j returning the vector d giving the distance from s to all other vertices and the vector p of predecessor vertices. The path from s to each vertex can be deduced from the p vector.

Determine the shortest path from vertex s to each vertex j returning the vector d giving the distance from s to all other vertices and the vector p of predecessor vertices. The path from s to each vertex can be deduced from the p vector.

Attributes

Generated with