10 Shortest Path Interview Questions and Answers

Shortest path algorithms are fundamental in computer science and are widely used in various applications such as network routing, geographic mapping, and logistics planning. These algorithms help determine the most efficient route between two points, optimizing for factors like distance, time, or cost. Understanding the principles behind shortest path algorithms is crucial for solving complex problems in both theoretical and practical domains.

This article provides a curated selection of interview questions focused on shortest path algorithms. By working through these questions, you will gain a deeper understanding of the concepts and techniques essential for tackling shortest path problems, thereby enhancing your problem-solving skills and technical proficiency.

Shortest Path Interview Questions and Answers

1. Implement Dijkstra’s algorithm to find the shortest path from a given source node to all other nodes in a graph with non-negative weights.

Dijkstra’s algorithm is a well-known method for finding the shortest path from a source node to all other nodes in a graph with non-negative weights. It maintains a set of nodes with known shortest distances from the source and repeatedly selects the node with the smallest known distance, updating the distances of its neighbors.

Here is a concise implementation of Dijkstra’s algorithm in Python:

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

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(graph, 'A'))
# Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

2. Write a function to implement the Bellman-Ford algorithm for finding the shortest path in a graph that may contain negative weights.

The Bellman-Ford algorithm iteratively relaxes all edges in the graph for a number of iterations equal to the number of vertices minus one. After these iterations, it checks for negative weight cycles by seeing if any edge can still be relaxed.

Here is a concise implementation of the Bellman-Ford algorithm in Python:

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []

    def add_edge(self, u, v, w):
        self.edges.append((u, v, w))

    def bellman_ford(self, src):
        dist = [float('inf')] * self.V
        dist[src] = 0

        for _ in range(self.V - 1):
            for u, v, w in self.edges:
                if dist[u] != float('inf') and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        for u, v, w in self.edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                print("Graph contains negative weight cycle")
                return

        return dist

# Example usage:
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)

distances = g.bellman_ford(0)
print(distances)

3. Explain the key differences between Dijkstra’s and Bellman-Ford algorithms, including their use cases and limitations.

Dijkstra’s and Bellman-Ford algorithms both find the shortest path in a graph but differ in approach, use cases, and limitations.

Dijkstra’s Algorithm:

• Use Case: Best for graphs with non-negative weights, commonly used in routing and navigation systems.
• Approach: Greedy, selecting the shortest path iteratively.
• Complexity: O(V^2) for a simple implementation and O(E + V log V) with a priority queue.
• Limitations: Cannot handle negative weight edges.

Bellman-Ford Algorithm:

• Use Case: Suitable for graphs with negative weight edges and can detect negative weight cycles.
• Approach: Dynamic programming, relaxing all edges up to V-1 times.
• Complexity: O(VE), less efficient for large graphs.
• Limitations: Slower compared to Dijkstra’s for graphs without negative weights.

4. Implement the A* search algorithm for finding the shortest path in a grid where some cells are blocked.

The A* search algorithm is used to find the shortest path between two points, combining Dijkstra’s algorithm and Greedy Best-First-Search by using a heuristic. It maintains a priority queue of nodes to explore, where the priority is determined by the sum of the cost to reach the node and the estimated cost to reach the goal.

Here is a concise implementation of the A* search algorithm for finding the shortest path in a grid where some cells are blocked:

import heapq

def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star_search(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    open_set = []
    heapq.heappush(open_set, (0, start))
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            neighbor = (current[0] + dx, current[1] + dy)
            if 0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols and grid[neighbor[0]][neighbor[1]] == 0:
                tentative_g_score = g_score[current] + 1
                if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
                    heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return None

grid = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

start = (0, 0)
goal = (4, 4)
path = a_star_search(grid, start, goal)
print(path)

5. Write a function to implement the Floyd-Warshall algorithm for finding shortest paths between all pairs of vertices in a graph.

The Floyd-Warshall algorithm is a dynamic programming method for finding the shortest paths between all pairs of vertices in a weighted graph. It iteratively improves the estimate of the shortest path between any two vertices by considering an intermediate vertex.

The algorithm has a time complexity of O(V^3) and is useful for dense graphs.

Here is a concise implementation of the Floyd-Warshall algorithm in Python:

def floyd_warshall(graph):
    V = len(graph)
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))

    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

# Example usage
graph = [
    [0, 3, float('inf'), 5],
    [2, 0, float('inf'), 4],
    [float('inf'), 1, 0, float('inf')],
    [float('inf'), float('inf'), 2, 0]
]

shortest_paths = floyd_warshall(graph)
for row in shortest_paths:
    print(row)

6. Compare the time complexities of Dijkstra’s, Bellman-Ford, and Floyd-Warshall algorithms. Which scenarios are each best suited for?

Dijkstra’s Algorithm:

• Time Complexity: O(V^2) with a simple array, O(E + V log V) with a priority queue
• Best Suited For: Graphs with non-negative weights, efficient for finding the shortest path from a single source to all other vertices.

Bellman-Ford Algorithm:

• Time Complexity: O(V * E)
• Best Suited For: Graphs with negative weights, can handle negative weight edges and detect negative weight cycles.

Floyd-Warshall Algorithm:

• Time Complexity: O(V^3)
• Best Suited For: Dense graphs, used to find the shortest paths between all pairs of vertices.

7. Optimize the implementation of Dijkstra’s algorithm using a priority queue. Provide the code and explain the improvements.

Dijkstra’s algorithm can be optimized using a priority queue, allowing for more efficient extraction of the node with the smallest tentative distance. This significantly improves performance compared to a linear search.

Here is an optimized implementation of Dijkstra’s algorithm using a priority queue:

import heapq

def dijkstra(graph, start):
    pq = [(0, start)]
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

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(graph, 'A'))
# Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

8. Implement Johnson’s algorithm for finding shortest paths in a sparse graph.

Johnson’s algorithm finds the shortest paths between all pairs of vertices in a sparse graph, even with negative edge weights. It involves adding a new vertex, using Bellman-Ford to reweight the graph, and then applying Dijkstra’s algorithm.

Here is a concise implementation of Johnson’s algorithm in Python:

import heapq

def johnson(graph):
    def bellman_ford(graph, source):
        distance = {v: float('inf') for v in graph}
        distance[source] = 0
        for _ in range(len(graph) - 1):
            for u in graph:
                for v, w in graph[u]:
                    if distance[u] + w < distance[v]:
                        distance[v] = distance[u] + w
        return distance

    def dijkstra(graph, source):
        distance = {v: float('inf') for v in graph}
        distance[source] = 0
        pq = [(0, source)]
        while pq:
            dist_u, u = heapq.heappop(pq)
            if dist_u > distance[u]:
                continue
            for v, w in graph[u]:
                if distance[u] + w < distance[v]:
                    distance[v] = distance[u] + w
                    heapq.heappush(pq, (distance[v], v))
        return distance

    new_vertex = 'new_vertex'
    graph[new_vertex] = [(v, 0) for v in graph]
    h = bellman_ford(graph, new_vertex)
    del graph[new_vertex]

    reweighted_graph = {}
    for u in graph:
        reweighted_graph[u] = []
        for v, w in graph[u]:
            reweighted_graph[u].append((v, w + h[u] - h[v]))

    distances = {}
    for u in reweighted_graph:
        distances[u] = dijkstra(reweighted_graph, u)
        for v in distances[u]:
            distances[u][v] += h[v] - h[u]

    return distances

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 2)],
    'C': [('D', 3)],
    'D': []
}

print(johnson(graph))

9. Analyze the trade-offs involved in the space and time complexities of Dijkstra’s, Bellman-Ford, and Floyd-Warshall algorithms.

Dijkstra’s Algorithm:

• Time Complexity: O(V^2) with a simple array, O(E + V log V) with a priority queue
• Space Complexity: O(V)
• Trade-offs: Efficient for graphs with non-negative weights but not suitable for negative weight edges.

Bellman-Ford Algorithm:

• Time Complexity: O(VE)
• Space Complexity: O(V)
• Trade-offs: Can handle negative weights and detect cycles but is slower for dense graphs.

Floyd-Warshall Algorithm:

• Time Complexity: O(V^3)
• Space Complexity: O(V^2)
• Trade-offs: Suitable for dense graphs but impractical for very large graphs due to cubic time complexity.

10. Write a function to detect if a graph contains a negative weight cycle and explain how this affects shortest path calculations.

A negative weight cycle in a graph is a cycle whose total weight is negative. This affects shortest path calculations because it allows for infinitely decreasing path lengths, causing algorithms to fail to converge.

To detect a negative weight cycle, the Bellman-Ford algorithm can be used. It finds the shortest paths from a single source vertex to all other vertices and detects negative weight cycles by checking for further relaxation.

Here is a concise example of detecting a negative weight cycle using the Bellman-Ford algorithm:

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def is_negative_weight_cycle(self, src):
        dist = [float("Inf")] * self.V
        dist[src] = 0

        for _ in range(self.V - 1):
            for u, v, w in self.graph:
                if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        for u, v, w in self.graph:
            if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                return True

        return False

g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(1, 2, -2)
g.add_edge(2, 3, -3)
g.add_edge(3, 4, -4)
g.add_edge(4, 1, -5)

print(g.is_negative_weight_cycle(0))  # Output: True