Minimum Cost to Visit Every Node in a Graph

Prereq: Bitmask Introduction

Output the minimum cost to traverse every node in a directed weighted graph. The graph will be in the form of a 2D list where each element [i,j] in the array denotes the weight of the directed edge from i to j. If the value is 0, then the edge doesn't exist. You do not have to end at the starting node. All edges are guaranteed to be in the range [0,1000]; there will not be more than 15 nodes in the graph. The starting node will always be node 0. If a solution does not exist, return -1.

Example:

Input:

1  [
2    [0, 100, 100, 1],
3    [0, 0, 100, 0],
4    [0, 1, 0, 0],
5    [0, 20, 1, 0]
6  ]

Output:

3

Explanation:

We need to traverse each node with the minimum possible cost.

Starting at node 0, we have the following possibilities:

  1. 0 -> 3 -> 2 -> 1:
  • Cost from 0 to 3 = 1
  • Cost from 3 to 2 = 1
  • Cost from 2 to 1 = 1
  • Total Cost = 3

  1. Any direct route from node 0 to nodes 1 or 2 has a cost of 100, which is already much higher than the previous total.

  2. Another possible route could be:

  • 0 -> 3 -> 1 -> 2:
    • Cost from 0 to 3 = 1
    • Cost from 3 to 1 = 20
    • Cost from 1 to 2 = 100
    • Total Cost = 121

Given the above, the minimum cost to traverse every node in the graph is via the route 0 -> 3 -> 2 -> 1 with a total cost of 3.

Try it yourself

←
↑TA 👨‍🏫