Implement Dijkstra’s shortest path algorithm for a given graph with a known source node.

A graph format is a dictionary of nodes as key and the value is a dictionary of neighbors to that node with the distance between them as follow.

Note: set the previous node of the source node to <code>None</code>.

Example:

Input:

<pre tabindex="0" class="chroma"><code>
source_node = &#39;A&#39;

graph = {
 &#39;A&#39;: {
 &#39;D&#39;: 1,
 &#39;B&#39;: 6
 },
 &#39;B&#39;: {
 &#39;A&#39;: 6,
 &#39;D&#39;: 2,
 &#39;E&#39;: 2,
 &#39;C&#39;: 5
 },
 &#39;C&#39;: {
 &#39;B&#39;: 5,
 &#39;E&#39;: 5
 },
 &#39;D&#39;: {
 &#39;A&#39;: 1,
 &#39;B&#39;: 2,
 &#39;E&#39;: 1
 },
 &#39;E&#39;: {
 &#39;C&#39;: 5,
 &#39;B&#39;: 2
 }

 }


</code></pre>

Output:

<pre tabindex="0" class="chroma"><code>
output_table = {
 &#39;A&#39;: {
 &#39;ShortestDistance&#39;: 0,
 &#39;PreviousVertex&#39;: None
 },
 &#39;B&#39;: {
 &#39;ShortestDistance&#39;: 3,
 &#39;PreviousVertex&#39;: &#39;D&#39;
 },
 &#39;C&#39;: {
 &#39;ShortestDistance&#39;: 7,
 &#39;PreviousVertex&#39;: &#39;E&#39;
 },
 &#39;D&#39;: {
 &#39;ShortestDistance&#39;: 1,
 &#39;PreviousVertex&#39;: &#39;A&#39;
 },
 &#39;E&#39;: {
 &#39;ShortestDistance&#39;: 2,
 &#39;PreviousVertex&#39;: &#39;D&#39;
 }
 }
</code></pre>

<img src="https://interviewquery-cms-images.s3-us-west-1.amazonaws.com/785715d4-3305-4b9f-bdd7-33d5cf987bdb.png" alt="image"/>

Implement Dijkstra's shortest path algorithm for a given graph with a known source node.

Dijkstra implementation

Comments