Please enable JavaScript.

Coggle requires JavaScript to display documents.

M12 - Coggle Diagram

- - - - We can use Floyd's Algorithm to generate the distance matrix. This algorithm is applicable to both undirected and directed weighted graphs, provided that they do not contain a cycle of negative length.
        
        Floyd's Algorithm computes the distance matrix of a weighted graph with n vertices through a series of n x n matrices. Each of these matrices contains the lengths of shortest paths with certain constraints on the paths considered for the matrix in question. Specifically:
        
        In particular, the series starts with D^(0), which does not allow any intermediate vertices in its paths; hence, D^(0) is simply the weight matrix of the graph.
        
        The last matrix in the series, D^(n), contains the length of the shortest paths among all paths that can use all n vertices as intermediate and hence is nothing other than the distance matrix being sought.
        
        The element dij^(k) in the ith row and the jth column of matrix D^(k) (i, j = 1, 2, ..., n, k = 0, 1, ..., n) is equal to the length of the shortest path among all paths from the ith vertex to the jth vertex with each intermediate vertex, if any, numbered not higher than k.
        
        We can compute all the elements of each matrix D^(k) from its immediate predecessor D^(k-1) in the series. Let dij^(k) be the element in the ith row and the jth column of matrix D^(k). This means that dij^(k) is equal to the length of the shortest path among all paths from the ith vertex vi to the jth vertex vj with their intermediate vertices numbered not higher than k:
        
        We can partition all such paths into two disjoint subsets: Those that do not use the kth vertex vk as intermediate and those that do.
        
        What is the length of the second subset? If the graph does not contain a cycle of negative length, we can limit our attention only to the paths in the second subset that use vertex vk as their intermediate vertex exactly once (because visiting vk more than once can only increase the path's length). All such paths have the following form:
        
        1 more item...
        
        Since the paths of the first subset have their intermediate vertices numbered not higher than k-1, the shortest of them is, by definition of our matrices, of length dij^(k-1).
        
        In other words, each of the paths is made up of a path from vi to vk with each intermediate vertex numbered not higher than k - 1 and a path from vk to vj with each intermediate vertex numbered not higher than k - 1.
        
        1 more item...
        
        (
        
        vi, a list of intermediate vertices each not numbered higher than k, vj.
        
        Series of Matrices:
        
        D^(0), ..., D^(k-1), D^(k), ..., D^(n)