You are given a weighted graph represented by an adjacency matrix graph where graph[i][j] represents the cost to move from node i to node j. Each node is labeled from 0 to n-1. You are also given two nodes source and destination.

Find the minimum cost to reach the destination node from the source node. If there is no path from the source to the destination, return -1.

Function Signature:

from typing import List

def min_cost_to_reach_destination(graph: List[List[int]], source: int, destination: int) -> int:
    """
    Find the minimum cost to reach the destination node from the source node.

    Parameters:
    - graph: A weighted graph represented by an adjacency matrix.
    - source: The source node.
    - destination: The destination node.

    Returns:
    - int: The minimum cost to reach the destination node, or -1 if there is no path.
    """
    # Your code here

Example:

graph = [
    [0, 10, 20, 0],
    [0, 0, 5, 10],
    [0, 0, 0, 20],
    [0, 0, 0, 0]
]

result = min_cost_to_reach_destination(graph, 0, 3)
print(result)  # Output: 20
assert result == 20  # Path: 0 --> 1 --> 3

result = min_cost_to_reach_destination(graph, 3, 0)
print(result)  # Output: -1
assert result == -1  # No path


graph = [
    [0, 10, 20, 0],
    [0, 0, 5, 10],
    [0, 0, 0, 2],
    [0, 0, 0, 0]
]

result = min_cost_to_reach_destination(graph, 0, 3)
print(result)  # Output: 17
assert result == 17  # Path: 0 --> 1 --> 2 --> 3

Instructions:

  • Write the min_cost_to_reach_destination function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊