Package pfvisualizer.algorithms

Class Dijkstra

  • All Implemented Interfaces:
    Pathfinder
    Direct Known Subclasses:
    AStar
    public class Dijkstra
extends java.lang.Object
implements Pathfinder
    Dijkstra's algorithm.

    • Constructor Summary

      Constructors 
      Constructor Description
      Dijkstra()  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected float getDistanceBetween​(Node first, Node second)
      Calculates the distance between two nodes.
      protected Node[] getSuccessors​(Node node)
      Returns a list of nodes that can be moved into from the given parent node.
      protected float heuristic​(Node node, Node end)
      Calculates the heuristic value which is an estimated distance between the given node and the end node.
      protected boolean isBlocked​(int row, int col)
      Checks if the given node is blocked (i.e wall).
      Result search​(int[][] grid, int startCol, int startRow, int endCol, int endRow)
      Performs a search for a path from given starting coordinates to the given end coordinates on the given grid.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • height

        protected int height

      • width

        protected int width

      • end

        protected Node end

      • grid

        protected int[][] grid

      • map

        protected int[][] map

      • directions

        protected int[][] directions

    • Constructor Detail

      • Dijkstra

        public Dijkstra()

    • Method Detail

      • heuristic

        protected float heuristic​(Node node,
                          Node end)
        Calculates the heuristic value which is an estimated distance between the given node and the end node.
        Parameters:
        node - start node
        end - end node
        Returns:
        the heuristic value

      • search

        public Result search​(int[][] grid,
                     int startCol,
                     int startRow,
                     int endCol,
                     int endRow)
        Description copied from interface: Pathfinder
        Performs a search for a path from given starting coordinates to the given end coordinates on the given grid.
        Specified by:
        search in interface Pathfinder
        Parameters:
        grid - map to perform the search on
        startCol - start column
        startRow - start row
        endCol - end column
        endRow - end row
        Returns:
        Result object which contains information such as the length of the optimal path

      • getDistanceBetween

        protected float getDistanceBetween​(Node first,
                                   Node second)
        Calculates the distance between two nodes.
        Parameters:
        first - first node
        second - second node
        Returns:
        distance between the given nodes

      • getSuccessors

        protected Node[] getSuccessors​(Node node)
        Returns a list of nodes that can be moved into from the given parent node.
        Parameters:
        node - the parent node
        Returns:
        list of nodes that can be moved into from the parent node

      • isBlocked

        protected boolean isBlocked​(int row,
                            int col)
        Checks if the given node is blocked (i.e wall).
        Parameters:
        row - row coordinate of the node
        col - column coordinate of the node
        Returns:
        a boolean representing whether the node is blocked or not