Steiner Tree Three Terminals

Problem

Compute the minimum weight of a connected subgraph spanning three terminals.

The optimal three-terminal Steiner tree is a star centered at some vertex when shortest-path distances are used, so run Floyd-Warshall and return the minimum over all v of dist(a, v) + dist(b, v) + dist(c, v). edges is a list of [u, v, weight] triples with non-negative weights and a, b, c are distinct terminals. Return -1 when no center connects all three.

Hint

Any branching point of a three-terminal tree is the meeting node of the three shortest paths.

Test cases

case 1

in: [4,[[0,1,1],[1,2,1],[2,3,1]],0,1,2]

expected: 2

case 2

in: [5,[[0,1,2],[1,2,2],[2,3,2],[3,4,2]],0,2,4]

expected: 8

case 3

in: [4,[[0,1,5],[1,2,5],[2,3,5],[0,3,1]],1,3,0]

expected: 6

case 4

in: [3,[[0,1,4]],0,1,2]

expected: -1

case 5

in: [3,[[0,1,1],[1,2,1],[2,0,1]],0,1,2]

expected: 2

Starter codePython

def steiner_three_terminal(n, edges, a, b, c):
    # Your code here
    pass

5 test cases · run your code against them in the editor