Creating a graph from only the edge lengths between nodes

userMkQS 0
Viewed 37

If there is a graph with N nodes and I'm only given a N*N matrix of the distances from each node to every other (the diagonal is of course 0), what would be the most efficient way of generating a graph with as few edges as possible?

for n = 4 and the matrix

0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0

only having 3 edges would be enough, all connected to the 1st node.

  • the edge from 1 and 2 would have length 1
  • the edge from 1 and 3 would have length 2
  • the edge from 1 and 4 would have length 3
stl graph-theory c++
2 Answers

" N*N matrix of the distances from each node to every other (the diagonal is of course 0)"

This is called the adjacency matrix. It completely specifies the graph. Each non-sero value defines an edge between two vertices. You cannot reduce the number of edges below the number of non zero value without changing the graph.

ravenspoint0

Simply create a full graph using the matrix as the incidence matrix, then remove unneeded edges.

Edge (a,b) is unneeded if and only if there is another path from a to b of the same length as (a,b). That is, if there is vertex c different from both a and b such that

distance(a,b) = distance(a,c) + distance(c,b)

This will not work if some distances not on the diagonal are zero or negative.

n. 1.8e9-where's-my-share m.0
Related