[Solved]: Algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality

Problem Detail: 

I am searching for an algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality( $\text{weight}(u,v) \le \text{weight}(u,w) + \text{weight}(w,v)$ for all vertices $u, v, w$).

My first naive try was to use an algorithm for solving the all-pairs-shortest-path-problem and compare the result to the vertices connecting two nodes directly.

However, I think this might be overkill. Is there any better way to check?

Thanks a lot.

Asked By : rog4

Answered By : D.W.

Yes. If you have a complete graph, the simplest algorithm is to enumerate all triangles and check whether each one satisfies the inequality. In practice, this will also likely be the best solution unless your graphs are very large and you need the absolute best possible performance. For instance, enumeration will likely be faster than most shortest-paths algorithms.

None of the shortest-path algorithms provide better asymptotic runtime; they are more complicated to implement; and they will be slower in practice (because of a larger constant factor).

As AJed correctly points out, you can use matrix multiplication to beat the $O(n^3)$ bound. However, this requires a bit more care. While there are algorithms for matrix multiplication that are faster than $O(n^3)$ time, the algorithms are tricky to implement, so if you take this approach, you might want to use an existing library/implementation (e.g., BLAS). Also, the asymptotically optimal algorithms (e.g., Coppersmith/Winograd, Stothers, Williams) only become faster once $n$ becomes extremely large so they won't be worthwhile in practice. This suggests that if you want to wring out every last bit of performance, you'll need to actually benchmark this on realistic workloads: asymptotic complexity can be misleading.

If you care about extreme optimization, cache effects may also play a huge role here, so the way the graph is laid out in memory may have a significant effect on the constant factors. Fortunately, if your graph is represented as an adjacency matrix, standard libraries for matrix multiplication already take this into account.

If it were me, I'd just enumerate all triangles and check the triangle inequality. If you run into a problem domain where this is the bottleneck in the overall computation and where it is too slow, then you could consider more sophisticated approaches, like using matrix multiplication, at that point. To paraphrase Knuth, "Premature optimization is the root of all evil".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16827