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)

What is a Network in the context of Graph?

Network refers to a graph in which the edges are bound with weights. Here weights can be numbers assigned to a the edges. Hence, a graph of this nature is referred to as weighted graph or a network.