Wiener Index - Calculation in Arbitrary Graphs

Calculation in Arbitrary Graphs

The Wiener index may be calculated directly using an algorithm for computing all pairwise distances in the graph. When the graph is unweighted (so the length of a path is just its number of edges), these distances may be calculated by repeating a breadth-first search algorithm, once for each starting vertex. The total time for this approach is O(nm), where n is the number of vertices in the graph and m is its number of edges.

For weighted graphs, one may instead use the Floyd–Warshall algorithm or Johnson's algorithm, with running time O(n3) or O(nm + n2 log n) respectively. Alternative but less efficient algorithms based on repeated matrix multiplication have also been developed within the chemical informatics literature.