Find shortest path using Dijkstra's Algorithm

The Dijkstra's algorithm entails the following procedure:
- The breath-first approach is used to traversal the network, however the difference here is instead of a queue data structure to store the traversed vertex this algorithm uses a priority queue. The priority queue helps to remove the items in order of values rather than in order of being added to the queue.
- Have an account of lowest total path weight (i.e. weightsum), from the start vertex to the target vertex
- Have an account of immediate predecessor in a given path for each vertex
- Have an account of the items in the priority queue

Exercise- Find the shortest path from Pori to Kuopio


1
----------------------------------------------------
Vertex - Weightsum - Predecessor
----------------------------------------------------
Helsinki - nul - null
Ivalo - null - null
Kouvola - null - null
Kuopio - 409 - Pori
Oulu - null - null
Pori - 0 - Pori
Tampere - 110 - Pori
Turku - 141 - Pori
----------------------------------------------------
Visited: Pori
Priority Queue: (Tampere,110), (Turku,141), (Kuopio,409)

2
----------------------------------------------------
Vertex - Weightsum - Predecessor
----------------------------------------------------
Helsinki - 287 - Tampere
Ivalo - null - null
Kouvola - null - null
Kuopio - 404 - Tampere
Oulu - null - null
Pori - 0 - Pori
Tampere - 110 - Pori
Turku - 141 - Pori
----------------------------------------------------
Visited: Pori,(Tampere,110)
Priority Queue: (Turku,141),(Helsinki,287),(Kuopio,404),(Kuopio,409)

3
----------------------------------------------------
Vertex - Weightsum - Predecessor
----------------------------------------------------
Helsinki - 287 - Tampere
Ivalo - null - null
Kouvola - null - null
Kuopio - 404 - Tampere
Oulu - null - null
Pori - 0 - Pori
Tampere - 110 - Pori
Turku - 141 - Pori
----------------------------------------------------
Visited: Pori,(Tampere,110),(Turku,141)
Priority Queue: (Helsinki,287),(Kuopio,404),(Kuopio,409)

4
----------------------------------------------------
Vertex - Weightsum - Predecessor
----------------------------------------------------
Helsinki - 287 - Tampere
Ivalo - null - null
Kouvola - 364 - Helsinki
Kuopio - 404 - Tampere
Oulu - null - null
Pori - 0 - Pori
Tampere - 110 - Pori
Turku - 141 - Pori
----------------------------------------------------
Visited: Pori,(Tampere,110),(Turku,141),(Helsinki,287)
Priority Queue: (Kouvola,364),(Kuopio,404),(Kuopio,409)

5
----------------------------------------------------
Vertex - Weightsum - Predecessor
----------------------------------------------------
Helsinki - 287 - Tampere
Ivalo - null - null
Kouvola - 364 - Helsinki
Kuopio - 404 - Tampere
Oulu - 898 - Kouvola
Pori - 0 - Pori
Tampere - 110 - Pori
Turku - 141 - Pori
----------------------------------------------------
Visited: Pori,(Tampere,110),(Turku,141),(Helsinki,287),(Kouvola,364)
Priority Queue: (Kuopio,404),(Kuopio,409),(Oulu,898)

6
----------------------------------------------------
Vertex - Weightsum - Predecessor
----------------------------------------------------
Helsinki - 287 - Tampere
Ivalo - null - null
Kouvola - 364 - Helsinki
Kuopio - 404 - Tampere
Oulu - 898 - Kouvola
Pori - 0 - Pori
Tampere - 110 - Pori
Turku - 141 - Pori
----------------------------------------------------
Visited: Pori,(Tampere,110),(Turku,141),(Helsinki,287),(Kouvola,364),(Kuopio,404)
Priority Queue: (Kuopio,409),(Oulu,898)

Therefore the shortest path from Pori to Kuopio is Pori,(Tampere,110),(Kuopio,404)

Graph Traversal Methods

There are two possible traversal methods for a graph:
i. Breadth-First Traversal
ii. Depth-First Traversal

i. Breadth-First Traversal: Traverse all the vertices starting from a given 'start vertex'. Hence, such a traversal follows the 'neighbour-first' principle by considering the following:
- No vertex is visited more than once
- Only those vertices that can be reached are visited

Importantly here, we make use of the Queue data structure. In effect, we house the vertices in the queue that are to be visited soon in the order which they are added to this queue i.e. first-in first-out.

Visiting a vertex involves returning the data item in the vertex and adding its neighbour vertices to the queue. However, we don't carryout any action under following conditions:
- if the neighbour is already present in the queue or if the neighbour has been already visited

As an example of the breadth-first traversal, we traverse the major cities of Finland with by the start vertex as 'Pori . Note! the neighbour(s) of a given vertex are added to the queue in alphabetical order.



1
Visited: Pori
Queue: Tampere, Turku

2
Visited: Pori, Tampere
Queue: Turku, Helsinki, Kuopio

3
Visited: Pori, Tampere, Turku
Queue: Helsinki, Kuopio

4
Visited: Pori, Tampere, Turku, Helsinki
Queue: Kuopio, Kouvola

5
Visited: Pori, Tampere, Turku, Helsinki, Kuopio
Queue: Kouvola

6
Visited: Pori, Tampere, Turku, Helsinki, Kuopio, Kouvola
Queue: Oulu

7
Visited: Pori, Tampere, Turku, Helsinki, Kuopio, Kouvola, Oulu
Queue: empty

Therefore, the route yielded by the Breadth-First traversal:
Pori, Tampere, Turku, Helsinki, Kuopio, Kouvola, Oulu


ii. Depth-First Traversal: Traverse all the vertices starting from a given 'start vertex'. Hence, such a traversal follows the 'neighbour-first' principle by considering the following:
- No vertex is visited more than once
- Only those vertices that can be reached are visited

Importantly here, we make use of the Stack data structure. In effect, we stack the vertices so that vertices to be visited soon are in order in which they are popped from the stack i.e. last-in, first-out.

Visiting a vertex involves returning the data item in the vertex and adding its neighbour vertices to the stack. However, we don't carryout any action if the following occurs:
- neighbour is already present in the stack or if the neighbour has already been visited


As an example of the depth-first traversal, we traverse the major cities of Finland with by the start vertex as 'Pori'. Note! the neighbour(s) of a given vertex are pushed to the stack in alphabetical order.

1
Visited: Pori
Stack:
-------
Turku
-------
Tampere
-------

2
Visited: Pori, Turku
Stack:
-------
Helsinki
-------
Tampere
-------

3
Visited: Pori, Turku, Helsinki
Stack:
-------
Kuopio
-------
Kouvola
-------
Tampere
-------

4
Visited: Pori, Turku, Helsinki, Kuopio
Stack:
-------
Kouvola
-------
Tampere
-------

5
Visited: Pori, Turku, Helsinki, Kuopio, Kouvola
Stack:
-------
Oulu
-------
Tampere
-------

6
Visited: Pori, Turku, Helsinki, Kuopio, Kouvola, Oulu
Stack:
-------
Tampere
-------

7
Visited: Pori, Turku, Helsinki, Kuopio, Kouvola, Oulu, Tampere
Stack:
-------
Empty
-------

Therefore, the route yielded by the Depth-First traversal:
Pori, Turku, Helsinki, Kuopio, Kouvola, Oulu, Tampere