Find the Shortest Distance in a Weighted Undirected Graph

Question

The question asks the candidate to find the shortest distance between two nodes in a weighted undirected graph using an appropriate algorithm.

Codemia · Accepted Answer

To find the shortest distance in a weighted undirected graph, I will use Dijkstra's algorithm. This algorithm is efficient for graphs with non-negative weights and works by exploring the closest unvisited node at each step, updating the shortest known distances to each node.

The implementation involves using a priority queue to always expand the least costly node. Here is a Python code snippet that demonstrates the algorithm:

```python
import heapq
from collections import defaultdict

def dijkstra(graph, start):
    min_heap = [(0, start)]  # (distance, node)
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    visited = set()

while min_heap:
        current_distance, current_node = heapq.heappop(min_heap)
        if current_node in visited:
            continue
        visited.add(current_node)

for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(min_heap, (distance, neighbor))

return distances
```
This code initializes distances and processes each node, updating the shortest paths.

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. The space complexity is O(V) due to the storage of distances and the priority queue.

It is important to consider edge cases such as:
1. Graphs with no edges, where the distance should be infinity for all nodes except the start.
2. Graphs with negative weight edges, which Dijkstra's algorithm cannot handle correctly. In such cases, the Bellman-Ford algorithm should be used instead.

In conclusion, Dijkstra's algorithm is a powerful method for finding the shortest path in weighted undirected graphs with non-negative weights. It is essential to understand the algorithm's limitations and choose the right approach based on the graph's characteristics.

Find the Shortest Distance in a Weighted Undirected Graph

Visa

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Visa Software Engineer I 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