Lenmatrix

Lenmatrix, or length matrix, is a matrix representation that records the shortest-path lengths between all pairs of vertices in a weighted graph. It abstracts the concept of distance in a network, providing a single data structure from which various analyses can be performed.

Formally, for a graph G=(V,E,w) with n=|V| vertices, the lenmatrix L is an n×n matrix where the entry L[i][j] equals the minimum total weight of any path from vertex i to vertex j. If i=j, L[i][i]=0; if no path exists, L[i][j] is infinite. In undirected graphs L is symmetric; in directed graphs the entries may differ, reflecting asymmetry of reachability.

Computation: L can be obtained by running the Floyd-Warshall algorithm in O(n^3) time, or by running Dijkstra's algorithm from every vertex in O(nm + n^2 log n) time for graphs with m edges. For sparse graphs Johnson's algorithm can be used to achieve O(n m log n).

Variants and relation: Lenmatrix is closely related to the distance matrix used in graph theory. In practice, the term lenmatrix is sometimes used interchangeably with distance matrix, though some authors distinguish between path length and hop-count matrices or normalized distance measures.

Properties: All entries are nonnegative; diagonal elements are zero; L[i][j] ≤ L[i][k] + L[k][j] (triangle inequality). For disconnected pairs L[i][j]=∞. In undirected graphs L is symmetric.

Applications: The lenmatrix supports routing optimizations, clustering and community detection, network reliability analysis, and centrality measures such as closeness centrality, which depend on pairwise distances between nodes.

Example: A simple graph with four vertices A,B,C,D and weighted edges A-B=2, B-C=4, C-D=2, A-D=7 yields the lenmatrix:

A: 0 2 6 7

B: 2 0 4 6

C: 6 4 0 2

D: 7 6 2 0