ea ' ' ' ' ' ' ' ' ' ' 'dd ' 'dc 'dd 'dd ' 'ee 'ec the algorithm finishes with the matrix of shortest distances and the matrix of associated predecessors so the shortest distance from to is and the predecessors of are ethen dthen cgiving the path note that updating distance does not necessarily mean updating the associated predecessor for examplewhen introducing as shortcut between and bthe predecessor of remains minimal spanning trees we now move on to another common graph-based problem suppose you have been given weighted undirected graph such as the followinga we could think of the vertices as representing housesand the weights as the distances between them now imagine that you are tasked with supplying all these houses with some commodity such as watergasor electricity for obvious reasonsyou will want to keep the amount of digging and laying of pipes or cable to minimum sowhat is the best pipe or cable layout that you can findi what layout has the shortest overall lengthobviouslywe will have to choose some of the edges to dig alongbut not all of them for exampleif we have already chosen the edge between and dand the one between and dthen there is no reason to also have the one between and more generallyit is clear that we want to avoid circles alsoassuming that we have only one feeding-in point (it is of no importance which of the vertices that is)we need the whole layout to be connected we have seen already that connected graph without circles is tree