Find shortest distance in graph

Question

Given a weighted, undirected graph represented as an adjacency list, write a function to find the shortest distance between two specified nodes using Dijkstra's algorithm. The function should take the graph, the starting node, and the target node as input and return the minimum distance as an integer. If there is no path between the nodes, return -1.

Codemia · Accepted Answer

To solve the problem of finding the shortest distance in a weighted, undirected graph, we can utilize Dijkstra's algorithm. This algorithm is well-suited for graphs with non-negative weights, allowing us to efficiently find the shortest path from a starting node to a target node. The key characteristic of Dijkstra's algorithm is that it explores paths based on the minimum accumulated weight, making it effective for this problem where we need to determine the shortest distance between two specified nodes.

1. **Initialization**: Start by creating a priority queue (min-heap) to store the nodes along with their current shortest distances. Initialize a dictionary to keep track of the shortest distances from the starting node to all other nodes, setting the distance to the starting node as 0 and all others as infinity.

2. **Priority Queue**: Push the starting node into the priority queue with a distance of 0.

3. **Algorithm Loop**: While the priority queue is not empty:
   - Pop the node with the smallest distance.
   - If this node is the target node, return the distance.
   - Otherwise, iterate through its neighbors (from the adjacency list). For each neighbor, calculate the new distance. If this new distance is smaller than the previously recorded distance in the dictionary, update the dictionary and push the neighbor into the priority queue.

4. **No Path Case**: If the priority queue is exhausted and the target node was never reached, return -1 to indicate that there is no path between the nodes.

```python
import heapq

def dijkstra(graph, start, target):
    # Initialize distances dictionary with infinity
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # Priority queue to manage exploration of nodes
    priority_queue = [(0, start)]  # (distance, node)

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

# If we reach the target node, return the distance
        if current_node == target:
            return current_distance

# If the distance is greater than the recorded shortest distance, skip
        if current_distance > distances[current_node]:
            continue

# Explore neighbors
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

# Only consider this new path if it is better
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

# Return -1 if the target node is unreachable
    return -1
```

The time complexity of Dijkstra's algorithm implemented with a priority queue is O((V + E) log V), where V is the number of vertices and E is the number of edges in the graph. This is due to the fact that each node is processed once and each edge is relaxed once.

The space complexity is O(V) because we are storing distances for all vertices and a priority queue that, in the worst case, stores all vertices.

1. **Disconnected Graph**: If the graph is disconnected (i.e., the target node is not reachable from the start node), the function should return -1. For example, if the graph has nodes that are completely isolated.

2. **Single Node**: If the start and target nodes are the same, the function should return 0, as the shortest distance to itself is zero.

3. **Negative Weight**: Although Dijkstra's algorithm does not handle negative weights, ensure that the input graph does not contain them; otherwise, the algorithm could give incorrect results.

Find shortest distance in graph

Goldman Sachs

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Goldman Sachs Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string