Package ons.util

Class Dijkstra

java.lang.Object
ons.util.Dijkstra
public class Dijkstra
extends java.lang.Object
Dijkstra's routing algorithm. For a given source node, the algorithm finds the path with lowest cost to every other vertex. The algorithm steps are the following: 1) Assign to every node a distance value. Set it to zero for the initial node and to infinity for all other nodes. 2) Mark all nodes as unvisited. Set initial node as current. 3) For current node, consider all its unvisited neighbors and calculate their tentative distance (from the initial node). If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance. 4) After all neighbors of the current node have been considered, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal. 5) If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node) as the next "current node" and continue from step 3.

  • Constructor Summary

    Constructors 
    Constructor Description
    Dijkstra()  

  • Method Summary

    Modifier and Type Method Description
    static int[] dijkstra​(WeightedGraphMultiWeight G, int s, int index)  
    static int[] dijkstra​(WeightedGraph G, int s)  
    static int[] dijkstra​(WeightedMultiGraphMultiWeight G, int s, int index)  
    static int[] dijkstra​(WeightedMultiGraph G, int s)  
    static int[] getShortestPath​(int[] pred, int src, int dst)
    Finds the shortest path between a source and a destination node.
    static int[] getShortestPath​(WeightedGraphMultiWeight G, int src, int dst, int index)
    Retrieves the shortest path between a source and a destination node, within a weighted graph.
    static int[] getShortestPath​(WeightedGraph G, int src, int dst)
    Retrieves the shortest path between a source and a destination node, within a weighted graph.
    static int[] getShortestPath​(WeightedMultiGraphMultiWeight G, int src, int dst, int index)
    Retrieves the shortest path between a source and a destination node, within a weighted graph.
    static int[] getShortestPath​(WeightedMultiGraph G, int src, int dst)
    Retrieves the shortest path between a source and a destination node, within a weighted graph.
    static void printPath​(int[] pred, int src, int dst)
    Prints the path between a source and a destination node.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

  • Method Details

    • dijkstra

      public static int[] dijkstra​(WeightedGraph G, int s)

    • getShortestPath

      public static int[] getShortestPath​(WeightedGraph G, int src, int dst)
      Retrieves the shortest path between a source and a destination node, within a weighted graph.
      Parameters:
      G - the weighted graph in which the shortest path will be found
      src - the source node
      dst - the destination node
      Returns:
      the shortest path, as a vector of integers that represent node coordinates

    • getShortestPath

      public static int[] getShortestPath​(int[] pred, int src, int dst)
      Finds the shortest path between a source and a destination node.
      Parameters:
      pred - list of the destination node's predecessors
      src - the source node
      dst - the destination node
      Returns:
      the shortest path

    • printPath

      public static void printPath​(int[] pred, int src, int dst)
      Prints the path between a source and a destination node.
      Parameters:
      pred - list of the destination node's predecessors
      src - the source node
      dst - the destination node

    • dijkstra

      public static int[] dijkstra​(WeightedMultiGraph G, int s)

    • getShortestPath

      public static int[] getShortestPath​(WeightedMultiGraph G, int src, int dst)
      Retrieves the shortest path between a source and a destination node, within a weighted graph.
      Parameters:
      G - the weighted graph in which the shortest path will be found
      src - the source node
      dst - the destination node
      Returns:
      the shortest path, as a vector of integers that represent node coordinates

    • dijkstra

      public static int[] dijkstra​(WeightedMultiGraphMultiWeight G, int s, int index)

    • getShortestPath

      public static int[] getShortestPath​(WeightedMultiGraphMultiWeight G, int src, int dst, int index)
      Retrieves the shortest path between a source and a destination node, within a weighted graph.
      Parameters:
      G - the weighted graph in which the shortest path will be found
      src - the source node
      dst - the destination node
      index - the index of multiWeight edge
      Returns:
      the shortest path, as a vector of integers that represent node coordinates

    • dijkstra

      public static int[] dijkstra​(WeightedGraphMultiWeight G, int s, int index)

    • getShortestPath

      public static int[] getShortestPath​(WeightedGraphMultiWeight G, int src, int dst, int index)
      Retrieves the shortest path between a source and a destination node, within a weighted graph.
      Parameters:
      G - the weighted graph in which the shortest path will be found
      src - the source node
      dst - the destination node
      index - the index of multiWeight edge
      Returns:
      the shortest path, as a vector of integers that represent node coordinates