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:

  [
    [0, 100, 100, 1],
    [0, 0, 100, 0],
    [0, 1, 0, 0],
    [0, 20, 1, 0]
  ]

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

2. 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.

3. 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