3108. Minimum Cost Walk in Weighted Graph - Detailed Explanation

Problem Statement

In this problem, you are given a weighted graph with a set of nodes and directed edges, where each edge has an associated cost. The task is to determine the minimum cost walk from a specified source node to a target node. A walk in this context can visit nodes multiple times (i.e., cycles are allowed) as long as it minimizes the total cost. It is assumed that all edge costs are non-negative (if negative edges were allowed, a different approach such as Bellman-Ford would be necessary). If the target is unreachable from the source, you should indicate that (for example, by returning -1).

Example

Suppose we have a graph with 5 nodes (indexed from 0 to 4) and the following directed edges (each represented as [u, v, cost]):

• [0, 1, 10]
• [0, 2, 3]
• [1, 2, 1]
• [2, 1, 4]
• [2, 3, 2]
• [1, 3, 2]
• [3, 4, 7]

If the source is node 0 and the target is node 4, one optimal walk is:

• 0 → 2 (cost 3)
• 2 → 3 (cost 2)
• 3 → 4 (cost 7)

The total minimum cost is 3 + 2 + 7 = 12.

Hints

1. Shortest Path Algorithms:
   When edge weights are non-negative, Dijkstra’s algorithm is efficient for finding the shortest (minimum cost) walk. It uses a priority queue to always extend the current least-cost path.

2. Graph Representation:
   Represent the graph using an adjacency list. For each node, maintain a list of pairs (neighbor, cost) that represent outgoing edges.

3. Relaxation Technique:
   Keep an array (or map) to store the minimum cost to reach each node from the source. As you process each node, update (relax) the cost for each neighboring node if a cheaper cost is found.

Approaches

Dijkstra's Algorithm

• Idea:
  Start from the source node and use a priority queue to repeatedly select the node with the current minimum cost. Update the cost to reach its neighbors if a shorter path is found. This works efficiently in O(m log n) time, where m is the number of edges and n is the number of nodes.

• Steps:

  1. Build the graph as an adjacency list.

  2. Initialize an array of distances with infinity and set the source distance to 0.

  3. Use a min-heap (priority queue) to process nodes by their current distance.

  4. For each node extracted, iterate over its neighbors and relax the edge.

  5. Stop when the target node is processed or the heap is empty.

  6. Return the distance to the target node (or -1 if unreachable).

Complexity Analysis

• Time Complexity:
  O(m log n), due to processing each edge with the priority queue operations.

• Space Complexity:
  O(n + m), to store the graph and the distance array.

Python Code

Java Code