UNDERSTANDING DIJKSTRA PATHFINDING ALGORITHM

We will look at using Dijkstra Pathfinding algorithm to solve for single source shortest path problem.
Dijkstra algorithm uses the Greedy Method. Greedy method is said to be an algorithmic paradigm that follows the problem solving approach of making the locally optimal choice at each stage with the hope of finding a global optimum. What this means is that the greedy method solves problems in stages, at each stage, it picks the best input that meets some given criteria, inputs that pass the criteria are considered in the next stage.
Greedy method is used to solve problems that have the following two properties:

• Greedy-choice property: a global optimum can be arrived at by selecting a local optimum.
• Optimal substructure: an optimal solution to the problem contains an optimal solution to its sub problem.

The procedure for Dijkstra Algorithm should look like this:

• Select a vertex
• Relax the vertex; relaxation means the vertex selected above, we explore its neighbouring vertices ie vertices that can be reached directly from the selected one, if the distance of the selected vertex “d[u]” plus the cost of exploring the neighbouring vertex “C(u, v)”, is less than the distance of the neighbouring vertex, we update the distance of that neighbour.

If (d[u] + C(u, v) < d[v])
d[v] = d[u] + C(u, v)

where u is the selected vertex and v is the neighbouring vertex.

• Store explored vertex and the parent vertex (ie the parent vertex means the previous vertex that was relaxed to get the smallest distance) in a data structure
• Pick neighbour with shortest distance
• Vertices that cannot be explored directly from the selected one will not be relaxed and should have an initial value of infinity.

Dijkstra algorithm is exploring each vertex at a time (ie divide the problem into stages) and picking the vertex with the smallest distance (locally optimal).
The sub paths of the shortest paths are the shortest sub paths- Optimal substructure.

Pseudo code:

Function Dijkstra(Graph, source)
    For each vertex v in Graph:
        dist[v] = infinity
        previous[v] = undefined
    dist[source] = 0
    A = set of all nodes in Graph
    While A is not empty: 
        u= node in A with smallest dist[]
        remove u from A
        for each neighbour v of u:
            alt= dist[u] + cost(u, v)
            if alt < dist[v]
                dist[v] = alt
                previous[v] = u
    return previous[]

Constraints of Dijkstra

• Assumes non-negative edges
• Follows the current shortest path and may end up exploring more nodes than it should Dijkstra assumes non negative weights, if any of the edges have a negative value, Dijkstra algorithm may or may not give you the shortest path, this constraint is somewhat tackled in the Bellman ford pathfinding algorithm. Follows the current shortest path, because Dijkstra has no way of knowing in which direction the destination node is at, it will follow the current shortest path and may end up visiting more nodes than it should, this problem is somewhat tackled in the A search algorithm.

A SEARCH

A search is like an improved version of Dijkstra’s algorithm. It follows similar procedures to Dijkstra but has some additional features. One of the constraints of Dijkstra is that it has no way of knowing what direction the destination is at and so it might visit more than it should. A search algorithm tries to solve this constraint by giving each node a heuristic value which shows the distance of the node from the destination, the closer the node to the destination node, the smaller the heuristic value. Each node in the graph will have the following properties:

• G cost: this is the cost of edge(s, v) where s is the source and v is the vertex, to put simply, it’s the distance from the node to the starting node.
• H cost: the distance from the node to the destination node.
• F value: G cost + H cost.

Pseudo code:

Initialise open and closed list
Make the start vertex current_vertex
Calculate F cost for start vertex
          While current_vertex is not the destination
                 For each vertex adjacent to current_vertex
                          If vertex not in closed list and not in open list then
                               Add vertex to open list
                               Calculate F value
                               If new F cost < existing F cost or there is no existing F value then
            Update F value
    Set parent to be current_vertex
                                 END if
                            END if
                     Next adjacent vertex
                     Add current_vertex to closed list
                     Remove vertex with lowest F value from open list and make current
              END while