Count shortest distance in graph

Question

Given a weighted, undirected graph represented as an adjacency list, write a function to compute the shortest distance between two specified nodes. The function should take the graph, the starting node, and the target node as input and return the shortest 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 between two nodes in a weighted, undirected graph, we can recognize that this is a classic shortest path problem suitable for graph traversal algorithms. The **Breadth-First Search (BFS)** algorithm is generally used for unweighted graphs; however, since we have a weighted graph, we should use **Dijkstra's Algorithm**, which is specifically designed for finding the shortest paths from a source node to all other nodes in a graph with non-negative weights. Dijkstra's algorithm utilizes a priority queue to efficiently get the next node with the shortest known distance.

1. **Initialize** a priority queue (min-heap) to store the distances of nodes from the start node.
2. **Set up a dictionary** to keep track of the shortest distance from the start node to each node. Initialize the distance to the start node as 0 and all other nodes as infinity.
3. **Insert the starting node** into the priority queue with its distance.
4. **While the priority queue is not empty**, do the following:
   - Extract the node with the smallest distance.
   - If this node is the target node, return its distance.
   - For each neighbor of the current node, calculate the tentative distance through the current node. If this distance is less than the recorded distance for the neighbor, update the distance and add the neighbor to the priority queue.
5. If we exit the loop without having returned the target node's distance, return -1, indicating that there is no path.

Here is the Python implementation of the above approach:

```python
import heapq

def dijkstra_shortest_distance(graph, start, target):
    # Priority queue for the next node to process
    queue = []
    # Dictionary to store the shortest distances to each node
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heapq.heappush(queue, (0, start))  # (distance, node)

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

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

# Process each neighbor of the current node
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            # If found a shorter path to neighbor
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

# If target is not reachable
    return -1
```

This function takes a graph represented as an adjacency list, a starting node, and a target node, and returns the shortest distance or -1 if no path exists.

The time complexity of Dijkstra's algorithm using 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 due to the fact that each vertex is processed once, and each edge is checked once. The log V factor comes from the operations on the priority queue. The space complexity is **O(V)** as we are storing the distances for each vertex and the priority queue.

1. **No Path Exists**: If the start and target nodes are disconnected, the function should correctly return -1.
2. **Start Equals Target**: If the start node is the same as the target node, the function should return 0 because the shortest distance to itself is zero.
3. **Graph with One Node**: If the graph consists of only one node, the function should return 0 when the start and target are the same and -1 if they are different. 
4. **Graph with Multiple Edges**: If there are multiple edges between two nodes, the algorithm should correctly identify the edge with the minimum weight.

Count shortest distance in graph

Microsoft

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

Microsoft 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