Deutsche Bank Interview Questions

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 None.

Example:

Input:

source_node = 'A'

graph = {
        'A': {
            'D': 1,
            'B': 6
        },
        'B': {
            'A': 6,
            'D': 2,
            'E': 2,
            'C': 5
        },
        'C': {
            'B': 5,
            'E': 5
        },
        'D': {
            'A': 1,
            'B': 2,
            'E': 1
        },
        'E': {
            'C': 5,
            'B': 2
        }

    }

Output:

output_table = {
        'A': {
            'ShortestDistance': 0,
            'PreviousVertex': None
        },
        'B': {
            'ShortestDistance': 3,
            'PreviousVertex': 'D'
        },
        'C': {
            'ShortestDistance': 7,
            'PreviousVertex': 'E'
        },
        'D': {
            'ShortestDistance': 1,
            'PreviousVertex': 'A'
        },
        'E': {
            'ShortestDistance': 2,
            'PreviousVertex': 'D'
        }
    }