Interview Questions Programming Dijkstra's Algorithm #1

Dijkstra's Algorithm #1

Dijkstra's algorithm is used for finding the shortest path in a weighted graph from a source node to all other nodes. It works by iteratively selecting the vertex u that has the smallest distance, relaxing all edges that go from u to its neighbors, and updating the distances to these neighbors if smaller distances are found.

Objective
You're given a weighted graph, represented as an adjacency list. Your task is to find the shortest path between two specified nodes using Dijkstra's algorithm.

def dijkstra_shortest_path(graph: dict, start: str, end: str) -> list:

    pass

Inputs

graph: A dictionary where the keys are node names (as strings), and the values are dictionaries containing adjacent nodes and the weights of the edges to those nodes.
start: A string representing the starting node.
end: A string representing the ending node.

Output
Return a list of nodes that form the shortest path from start to end. If there's no path, return 'None'.

Example
For the graph defined as:

graph = {

    'A': {'B': 1, 'C': 4},

    'B': {'A': 1, 'C': 2, 'D': 5},

    'C': {'A': 4, 'B': 2, 'D': 1},

    'D': {'B': 5, 'C': 1}

}

The function call dijkstra_shortest_path(graph, 'A', 'D') should return ['A', 'B', 'C', 'D'] as this is the shortest path from 'A' to 'D'.

The distance from 'A' to 'B' is 1
The distance from 'B' to 'C' is 2
The distance from 'C' to 'D' is 1

If you add these up, the total distance from 'A' to 'D' through this path is 1 + 2 + 1 = 4. No other path from 'A' to 'D' gives a shorter distance, so Dijkstra's algorithm identifies this as the shortest path.

For more information, take a look at this video.

Notes
Write an efficient algorithm. A graph can have over 1000 nodes and the edge weights are positive integers.

Hint

Solution

Solution 1: Importing packages allowed

import heapq



# Implement Dijkstra's algorithm for shortest path

def dijkstra_shortest_path(graph: dict, start: str, end: str) -> list:

    # Initialize distance dictionary with infinite distance for all nodes except the start node

    distance = {node: float('inf') for node in graph}

    distance[start] = 0

    

    # Priority queue to keep track of nodes to be explored (distance, node)

    pq = [(0, start)]

    

    # Dictionary to keep track of predecessors for each node

    predecessors = {node: None for node in graph}

    

    while pq:

        # Get the node with the smallest distance from the priority queue

        current_distance, current_node = heapq.heappop(pq)

        

        # If this node is the end node, we are done

        if current_node == end:

            path = []

            while current_node is not None:

                path.insert(0, current_node)

                current_node = predecessors[current_node]

            return path

        

        # Explore neighbors

        for neighbor, weight in graph[current_node].items():

            new_distance = current_distance + weight

            

            # Update distance if a shorter path is found

            if new_distance < distance[neighbor]:

                distance[neighbor] = new_distance

                predecessors[neighbor] = current_node

                heapq.heappush(pq, (new_distance, neighbor))

    

    # If we reach here, there is no path from start to end

    return None



# Test the function

test_graph = {

    'A': {'B': 1, 'C': 4},

    'B': {'A': 1, 'C': 2, 'D': 5},

    'C': {'A': 4, 'B': 2, 'D': 1},

    'D': {'B': 5, 'C': 1}

}

print(dijkstra_shortest_path(test_graph, 'A', 'D'))  # Should return ['A', 'B', 'C', 'D']

Solution 2: Without importing packages

# Implement Dijkstra's algorithm for shortest path without external packages

def dijkstra_shortest_path_no_heap(graph: dict, start: str, end: str) -> list:

    # Initialize distance dictionary with infinite distance for all nodes except the start node

    distance = {node: float('inf') for node in graph}

    distance[start] = 0

    

    # Set to keep track of visited nodes

    visited = set()

    

    # Dictionary to keep track of predecessors for each node

    predecessors = {node: None for node in graph}

    

    # Current node to explore

    current_node = start

    

    while current_node is not None:

        # Mark the current node as visited

        visited.add(current_node)

        

        # If this node is the end node, we are done

        if current_node == end:

            path = []

            while current_node is not None:

                path.insert(0, current_node)

                current_node = predecessors[current_node]

            return path

        

        # Explore neighbors

        for neighbor, weight in graph[current_node].items():

            new_distance = distance[current_node] + weight

            

            # Update distance if a shorter path is found

            if new_distance < distance[neighbor]:

                distance[neighbor] = new_distance

                predecessors[neighbor] = current_node

        

        # Select the unvisited node with the smallest distance as the next node to visit

        candidates = {node: dist for node, dist in distance.items() if node not in visited}

        current_node = min(candidates, key=candidates.get, default=None)

    

    # If we reach here, there is no path from start to end

    return None



# Test the function

test_graph = {

    'A': {'B': 1, 'C': 4},

    'B': {'A': 1, 'C': 2, 'D': 5},

    'C': {'A': 4, 'B': 2, 'D': 1},

    'D': {'B': 5, 'C': 1}

}

print(dijkstra_shortest_path_no_heap(test_graph, 'A', 'D'))  # Should return ['A', 'B', 'C', 'D']

Title	Category	Subcategory	Difficulty	Status
Dijkstra's Algorithm #2	Programming	Graphs	Hard	Unlock
Find All Paths	Programming	Graphs	Hard	Unlock
Minimum Spanning Tree (MST)	Programming	Graphs	Hard	Unlock

The Interview Guide for Quants and Traders

The Interview Guide for Quants and Traders