Katkat
Back

Compute shortest path in cyclic graph

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to implement a shortest-path algorithm in a directed graph that may contain cycles, specifically evaluating the selection between Dijkstra's algorithm and Bellman-Ford based on edge weight constraints.

Shortest Path in a Cyclic Graph

You are given a directed graph represented as a list of edges, where each edge [u, v, w] indicates a directed path from node u to node v with weight w. The graph may contain cycles and self-loops. Your goal is to find the shortest distance from a starting node source to all other nodes in the graph.

Function Signature

def get_shortest_paths(n, edges, source):

Parameters

  • n: The number of nodes in the graph (labeled 0 to n-1).
  • edges: A list of lists where each sub-list is [u, v, w].
  • source: The starting node index.

Requirements

  1. Return a list of length n where index i contains the shortest path distance from source to i.
  2. If a node is unreachable, return float('inf') for that index.
  3. Assume all weights w are non-negative.
  4. If a negative cycle exists, the function should identify it and raise a ValueError.

Example

Input: n = 4, edges = [[0, 1, 5], [1, 2, 2], [2, 3, 1], [0, 3, 10]], source = 0
Output: [0, 5, 7, 8]
# Explanation: 0->1 is 5, 0->1->2 is 7, 0->1->2->3 is 8. Direct 0->3 is 10, so 8 is chosen.

Edge Cases

  • Disconnected components.
  • Graphs with cycles (but no negative weights).
  • Self-loops (e.g., [1, 1, 5]).
  • Single node graph.

Hints

Hint 1

Since the graph contains cycles but edge weights are non-negative, Dijkstra's algorithm is the most efficient approach.

Hint 2

Use a min-priority queue to keep track of the node with the smallest known distance that has not yet been processed.

Hint 3

If negative edge weights were allowed, you would need to use the Bellman-Ford algorithm to handle cycles correctly.

Follow-up questions

  • How would your implementation change if the graph contained negative edge weights but no negative cycles?
  • What is the time complexity of your solution, and how does it change if you use a simple list instead of a priority queue?
  • How would you modify the algorithm to return the actual path (the sequence of nodes) rather than just the total distance?