Find shortest distance in graph

Question

Given a weighted, undirected graph represented as an adjacency list, implement an algorithm to find the shortest distance between two specified nodes. Your solution should return the shortest distance as an integer, or -1 if there is no path between the nodes.

Codemia · Accepted Answer

For this problem, we are tasked with finding the shortest distance between two nodes in a weighted, undirected graph represented as an adjacency list. The best approach to solve this problem is to utilize Dijkstra's algorithm. This algorithm is particularly suited for graphs with non-negative weights and is efficient in finding the shortest path from a source node to all other nodes in the graph. The graph's adjacency list representation allows for easy access to neighboring nodes and their associated weights, enabling efficient traversal and pathfinding.

1. **Initialization**: Start by initializing a priority queue (min-heap) to keep track of the nodes to visit, along with their current distances from the source node. Also, create a distance dictionary to store the shortest distance to each node, initializing all distances to infinity, except for the source node which is set to 0.

2. **Add the source node to the priority queue**: Push the source node along with its distance (0) into the priority queue.

3. **Process the graph**: While the priority queue is not empty, perform the following:
   - Pop the node with the smallest distance from the priority queue.
   - If this node is the target node, return its distance as the shortest path.
   - For each neighboring node, calculate the potential new distance through the current node. If this distance is shorter than the previously known distance, update the distance and push the neighboring node into the priority queue.

4. **Handle no path case**: If you exit the loop without having reached the target node, return -1, indicating that there is no path between the source and target nodes.

**Example**: For a graph represented as `{0: [(1, 4), (2, 1)], 1: [(0, 4), (2, 2), (3, 1)], 2: [(0, 1), (1, 2), (3, 5)], 3: [(1, 1), (2, 5)]}`, if we need to find the shortest path from node 0 to node 3, the algorithm will yield a distance of 5 through the path 0 -> 2 -> 1 -> 3.

```python
import heapq
from collections import defaultdict

def shortest_distance(graph, start, end):
    # Initialize the priority queue and distances dictionary
    min_heap = []
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heapq.heappush(min_heap, (0, start))  # (distance, node)
    
    while min_heap:
        current_distance, current_node = heapq.heappop(min_heap)
        
        # If we reached the end node, return the distance
        if current_node == end:
            return current_distance
        
        # Check if the popped node's distance is greater than the recorded distance
        if current_distance > distances[current_node]:
            continue
        
        # Explore neighbors
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(min_heap, (distance, neighbor))
    
    # If we get here, there is no path to the end node
    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. This is because each vertex is pushed and popped from the priority queue once, and each edge is examined at most once. The space complexity is O(V) for storing the distances and the priority queue. Given that we are only storing distances for the nodes in the graph, this is efficient in terms of space usage.

1. **No Path**: The algorithm should return -1 if there is no path between the start and end nodes, for example, if the graph consists of disconnected components.
2. **Same Node**: If the start and end nodes are the same, the shortest distance should be 0, as no travel is needed.
3. **Negative Weights**: Although this problem specifies a weighted graph, if there are any negative weights, Dijkstra's algorithm will not function correctly, and we should handle or validate input accordingly. 
4. **Empty Graph**: If the graph is empty, the function should appropriately handle this case, possibly by returning -1 or raising an exception.

Find shortest distance in graph

Atlassian

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

Atlassian Software 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