<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Jeppe Holt on Medium]]></title>
        <description><![CDATA[Stories by Jeppe Holt on Medium]]></description>
        <link>https://medium.com/@jeppeholt?source=rss-e5bd683f473d------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*SNpvgBSZ76xV41PN.</url>
            <title>Stories by Jeppe Holt on Medium</title>
            <link>https://medium.com/@jeppeholt?source=rss-e5bd683f473d------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 03:49:19 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@jeppeholt/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Floyed-Warshall algorithm by-hand]]></title>
            <link>https://jeppeholt.medium.com/floyed-warshall-algorithm-by-hand-2c942bde739a?source=rss-e5bd683f473d------2</link>
            <guid isPermaLink="false">https://medium.com/p/2c942bde739a</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[shortest-path]]></category>
            <category><![CDATA[floyd-warshall]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[graph]]></category>
            <dc:creator><![CDATA[Jeppe Holt]]></dc:creator>
            <pubDate>Sun, 04 Jul 2021 20:49:54 GMT</pubDate>
            <atom:updated>2021-07-04T20:49:54.569Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ye-03vRsMs1APmYUsFjWhQ.jpeg" /></figure><p>While it’s is generally enough to simply understand what an algorithm takes as parameters and what it returns, a deeper understanding of it is often useful. Personally i prefer to get this understanding by doing the calculation for an example by hand, as this forces me to really understand each step of the algorithm.</p><h4>What is the Floyed-Warshall algorithm</h4><p>The Floyed-Warshall algorithm is an algorithm for finding the shortest path in a directed weighted graph. The algorithm takes a directed graph matrix representation as input and then updates this matrix as shorter paths to each node is found. Finally it returns an updated matrix representing the shortest path from for each pair of nodes in the graph. Below the algorithm implemented in python can be seen.</p><pre>V <strong>=</strong> Number of vertices in the graph<br>INF <strong>=</strong> 99999</pre><pre><strong>def</strong> floydWarshall(graph):<br>    dist <strong>=</strong> list(map(<strong>lambda</strong> i: list(map(<strong>lambda</strong> j: j, i)), graph))</pre><pre><strong>    for</strong> k <strong>in</strong> range(V):<br>        <strong>for</strong> i <strong>in</strong> range(V):<br>            <strong>for</strong> j <strong>in</strong> range(V):<br>                dist[i][j] <strong>=</strong> min(dist[i][j],dist[i][k] <strong>+</strong> dist[k][j])</pre><pre>    return dist</pre><h4>Floyed-Warshall input</h4><p>As can be seen in the algorithm the input is simply a graph, but this is sort of ambiguous so im going to show and explain what form this graph should be in and how to derive it from a normal representation. The input expected in the above algorithm is matrix, which is essentially a list of lists. An example of this in python could be like this:</p><pre>graph = [[0,INF,INF,INF,-1,INF],<br>         [1,0,INF,2,INF,INF],<br>         [INF,2,0,INF,INF,-8],<br>         [-4,INF,INF,0,3,INF],<br>         [INF,7,INF,INF,0,INF],<br>         [INF,5,10,INF,INF,0]]</pre><p>This should be the form of the input to the algorithm, but as its is now without knowing how it is derived it, might seem like nonsense.</p><p>The graph that the above matrix corresponds to can be seen here:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/543/1*MoI6psXUIMwstrmP_4oo5g.png" /></figure><p>Now how is the shown matrix derived from this graph?</p><p>To show this i will provide a matrix with a bit more information, and then go trough each line to explain the method.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/342/1*z2HZ-dH_2pezOzfMudVKWg.png" /><figcaption>Equivalent matrix to the above, just with the different pairs shown</figcaption></figure><p>So the only difference from the first matrix an this one is that the different pairs can be read from here.</p><p>Now to actually look mat how this matrix can be constructed, this can easily be done line by line. So lets start with looking at the first line:</p><pre>[0,INF,INF,INF,-1,INF]</pre><p>This is basically the distance from the node A to any other node in the graph if a single transition is allowed. The tradition A to A is 0 because we already are in A, the cells with INF written are non-reachable nodes. The -1 is the transition from A to E. This is how the matrix is constructed, ill just take one more line:</p><pre>[1,0,INF,2,INF,INF]</pre><p>B has a transition to A with a weight of 1. Again a transition to itself will always be 0. There exists no transition from B to C. There is a transition from B to D with a weight of 2. The rest are INF as there exist no single transition from B to either E or F.</p><p>This is basically how you would construct the matrix by hand, now to the actual algorithm.</p><h4>The calculations</h4><p>The idea is that we take the first row and column, and see if there are are any possible paths shorter than the ones already in the matrix, if there are we update the matrix. Then we continue with the second row and column.</p><p>Now ill show the approach with the above graph. So we have the initial matrix and we will look at the first row and first column, as marked with orange.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/287/1*moBlLc3UljUXl-pRgCgEcg.png" /></figure><p>What i like to do here is to write all the selected pair up, as it makes it a bit more systematic to see the new possible transitions.</p><pre>(A,E)= -1, (B,A)= 1, (D,A)= -4</pre><p>Looking at the pairs we can see two new transitions namely B to E, and D to E. The way i usually notate this is like so:</p><pre>(B,A)+(A,E)=(B,E)=0, (D,A)+(A,E)=(D,E)=-5</pre><p>Thus we have discovered two new transition we can update the matrix with. We should also notice here that the transition (D,E) already exists, but since we have found a new transition with a smaller weight of only -5 we will override the old values as the goal is to find the shortest path. The updates are highlighted in cyan.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/287/1*WjrolE4Y0r1JNe-mGzsLeg.png" /><figcaption>Updated matrix, for (B,E) and (D,E)</figcaption></figure><p>The next step would the be the same, but with the second row and column instead as seen here:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/287/1*uUCtk-cC5N2QSX_5fgQWxg.png" /></figure><p>Again we find all the pairs in the selected parts:</p><pre>(B,A)=1, (B,D)=2, (B,E)=0, (C,B)=2, (E,B)=7, (F,B)=5</pre><p>Now we look for new transitions:</p><pre>(C,B)+(B,A)=(C,A)=3, (C,B)+(B,D)=(C,D)=3, (C,B)+(B,E)=(C,E)=2,<br>(E,B)+(B,A)=(E,A)=8, (E,B)+(B,D)=(E,D)=9,<br>(F,B)+(B,A)=(F,A)=3, (F,B)+(B,D)=(F,D)=3, (F,B)+(B,E)=(F,E)=7</pre><p>Here alot of new transitions were found which results in this matrix:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/262/1*TnmV0pYHdrjnEBb8Pup-Dw.png" /></figure><p>Following this approach for the remaining rows and columns the shortest path for each pair will be in the matrix.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2c942bde739a" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>