-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathfloyd-warshall-algorithm.html
More file actions
106 lines (100 loc) · 53.8 KB
/
floyd-warshall-algorithm.html
File metadata and controls
106 lines (100 loc) · 53.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Floyd-Warshall Algorithm</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="All Pair Shortest Path Algorithm">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Floyd-Warshall Algorithm">
<meta property="og:description" content="All Pair Shortest Path Algorithm">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/floyd-warshall-algorithm.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Floyd-Warshall Algorithm">
<meta name="twitter:description" content="All Pair Shortest Path Algorithm">
<meta name="twitter:url" content="/algorithm/floyd-warshall-algorithm.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/37.fb96070b.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" aria-current="page" class="active sidebar-link">Floyd-Warshall Algorithm</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/floyd-warshall-algorithm.html#all-pair-shortest-path-algorithm" class="sidebar-link">All Pair Shortest Path Algorithm</a></li></ul></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="floyd-warshall-algorithm"><a href="#floyd-warshall-algorithm" class="header-anchor">#</a> Floyd-Warshall Algorithm</h1> <h2 id="all-pair-shortest-path-algorithm"><a href="#all-pair-shortest-path-algorithm" class="header-anchor">#</a> All Pair Shortest Path Algorithm</h2> <p><a href="https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" target="_blank" rel="noopener noreferrer">Floyd-Warshall<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>'s algorithm is for finding shortest paths in a weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pair of vertices. With a little variation, it can print the shortest path and can detect negative cycles in a graph. Floyd-Warshall is a Dynamic-Programming algorithm.</p> <p>Let's look at an example. We're going to apply Floyd-Warshall's algorithm on this graph:<a href="http://i.stack.imgur.com/heaAS.png" target="_blank" rel="noopener noreferrer"><img src="http://i.stack.imgur.com/heaAS.png" alt="Example Graph"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>First thing we do is, we take two 2D matrices. These are <a href="http://stackoverflow.com/documentation/algorithm/2299/graphs/23963/storing-graphs-adjacency-matrix" target="_blank" rel="noopener noreferrer">adjacency matrices<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>. The size of the matrices is going to be the total number of vertices. For our graph, we will take <strong>4 * 4</strong> matrices. The <strong>Distance Matrix</strong> is going to store the minimum distance found so far between two vertices. At first, for the edges, if there is an edge between <strong>u-v</strong> and the distance/weight is <strong>w</strong>, we'll store: <code>distance[u][v] = w</code>. For all the edges that doesn't exist, we're gonna put <strong>infinity</strong>. The <strong>Path Matrix</strong> is for regenerating minimum distance path between two vertices. So initially, if there is a path between <strong>u</strong> and <strong>v</strong>, we're going to put <code>path[u][v] = u</code>. This means the best way to come to <strong>vertex-v</strong> from <strong>vertex-u</strong> is to use the edge that connects <strong>v</strong> with <strong>u</strong>. If there is no path between two vertices, we're going to put <strong>N</strong> there indicating there is no path available now. The two tables for our graph will look like:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token number">6</span> <span class="token operator">|</span> <span class="token number">15</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> N <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> inf <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token operator">-</span><span class="token number">2</span> <span class="token operator">|</span> inf <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> N <span class="token operator">|</span> N <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> N <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> inf <span class="token operator">|</span> inf <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> N <span class="token operator">|</span> N <span class="token operator">|</span> N <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> inf <span class="token operator">|</span> inf <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> N <span class="token operator">|</span> N <span class="token operator">|</span> N <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
distance path
</code></pre></div><p>Since there is no loop, the diagonals are set <strong>N</strong>. And the distance from the vertex itself is <strong>0</strong>.</p> <p>To apply Floyd-Warshall algorithm, we're going to select a middle vertex <strong>k</strong>. Then for each vertex <strong>i</strong>, we're going to check if we can go from <strong>i</strong> to <strong>k</strong> and then <strong>k</strong> to <strong>j</strong>, where <strong>j</strong> is another vertex and minimize the cost of going from <strong>i</strong> to <strong>j</strong>. If the current <strong>distance[i][j]</strong> is greater than <strong>distance[i][k]</strong> + <strong>distance[k][j]</strong>, we're going to put <strong>distance[i][j]</strong> equals to the summation of those two distances. And the <strong>path[i][j]</strong> will be set to <strong>path[k][j]</strong>, as it is better to go from <strong>i</strong> to <strong>k</strong>, and then <strong>k</strong> to <strong>j</strong>. All the vertices will be selected as <strong>k</strong>. We'll have 3 nested loops: for <strong>k</strong> going from 1 to 4, <strong>i</strong> going from 1 to 4 and <strong>j</strong> going from 1 to 4. We're going check:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">if</span> distance<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">></span> distance<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">+</span> distance<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
distance<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> distance<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">+</span> distance<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
path<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> path<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
end <span class="token keyword">if</span>
</code></pre></div><p>So what we're basically checking is, <strong>for every pair of vertices, do we get a shorter distance by going through another vertex?</strong> The total number of operations for our graph will be <strong>4 * 4 * 4</strong> = <strong>64</strong>. That means we're going to do this check <strong>64</strong> times. Let's look at a few of them:</p> <p>When <strong>k</strong> = <strong>1</strong>, <strong>i</strong> = <strong>2</strong> and <strong>j</strong> = <strong>3</strong>, <strong>distance[i][j]</strong> is <strong>-2</strong>, which is not greater than <strong>distance[i][k]</strong> + <strong>distance[k][j]</strong> = <strong>-2</strong> + <strong>0</strong> = <strong>-2</strong>. So it will remain unchanged. Again, when <strong>k</strong> = <strong>1</strong>, <strong>i</strong> = <strong>4</strong> and <strong>j</strong> = <strong>2</strong>, <strong>distance[i][j]</strong> = <strong>infinity</strong>, which is greater than <strong>distance[i][k]</strong> + <strong>distance[k][j]</strong> = <strong>1</strong> + <strong>3</strong> = <strong>4</strong>. So we put <strong>distance[i][j]</strong> = <strong>4</strong>, and we put <strong>path[i][j]</strong> = <strong>path[k][j]</strong> = <strong>1</strong>. What this means is, to go from <strong>vertex-4</strong> to <strong>vertex-2</strong>, the path <strong>4->1->2</strong> is shorter than the existing path. This is how we populate both matrices. The calculation for each step is shown <a href="http://imgur.com/a/NU6Hg" target="_blank" rel="noopener noreferrer">here<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>. After making necessary changes, our matrices will look like:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> N <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token operator">-</span><span class="token number">2</span> <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> N <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token number">6</span> <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> N <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> N <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span> <span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
distance path
</code></pre></div><p>This is our shortest distance matrix. For example, the shortest distance from <strong>1</strong> to <strong>4</strong> is <strong>3</strong> and the shortest distance between <strong>4</strong> to <strong>3</strong> is <strong>2</strong>. Our pseudo-code will be:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>Procedure Floyd<span class="token operator">-</span><span class="token function">Warshall</span><span class="token punctuation">(</span>Graph<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">for</span> k from <span class="token number">1</span> to V <span class="token comment">// V denotes the number of vertex</span>
<span class="token keyword">for</span> i from <span class="token number">1</span> to V
<span class="token keyword">for</span> j from <span class="token number">1</span> to V
<span class="token keyword">if</span> distance<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">></span> distance<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">+</span> distance<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
distance<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> distance<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">+</span> distance<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
path<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> path<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
end <span class="token keyword">if</span>
end <span class="token keyword">for</span>
end <span class="token keyword">for</span>
end <span class="token keyword">for</span>
</code></pre></div><p><strong>Printing the path:</strong></p> <p>To print the path, we'll check the <strong>Path</strong> matrix. To print the path from <strong>u</strong> to <strong>v</strong>, we'll start from <strong>path[u][v]</strong>. We'll set keep changing <strong>v</strong> = <strong>path[u][v]</strong> until we find <strong>path[u][v]</strong> = <strong>u</strong> and push every values of <strong>path[u][v]</strong> in a stack. After finding <strong>u</strong>, we'll print <strong>u</strong> and start popping items from the stack and print them. This works because the <strong>path</strong> matrix stores the value of the vertex which shares the shortest path to <strong>v</strong> from any other node. The pseudo-code will be:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>Procedure <span class="token function">PrintPath</span><span class="token punctuation">(</span>source<span class="token punctuation">,</span> destination<span class="token punctuation">)</span><span class="token operator">:</span>
s <span class="token operator">=</span> <span class="token function">Stack</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
S<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>destination<span class="token punctuation">)</span>
<span class="token keyword">while</span> Path<span class="token punctuation">[</span>source<span class="token punctuation">]</span><span class="token punctuation">[</span>destination<span class="token punctuation">]</span> is <span class="token operator">not</span> equal to source
S<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>Path<span class="token punctuation">[</span>source<span class="token punctuation">]</span><span class="token punctuation">[</span>destination<span class="token punctuation">]</span><span class="token punctuation">)</span>
destination <span class="token operator">:</span><span class="token operator">=</span> Path<span class="token punctuation">[</span>source<span class="token punctuation">]</span><span class="token punctuation">[</span>destination<span class="token punctuation">]</span>
end <span class="token keyword">while</span>
print <span class="token operator">-></span> source
<span class="token keyword">while</span> S is <span class="token operator">not</span> empty
print <span class="token operator">-></span> S<span class="token punctuation">.</span>pop
end <span class="token keyword">while</span>
</code></pre></div><p><strong>Finding Negative Edge Cycle:</strong></p> <p>To find out if there is a negative edge cycle, we'll need to check the main diagonal of <strong>distance</strong> matrix. If any value on the diagonal is negative, that means there is a negative cycle in the graph.</p> <p><strong>Complexity:</strong></p> <p>The complexity of Floyd-Warshall algorithm is <strong>O(V³)</strong> and the space complexity is: <strong>O(V²)</strong>.</p></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/floyd-warshall-algorithm.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/line-algorithm.html" class="prev">
Line Algorithm
</a></span> <span class="next"><a href="/algorithm/catalan-number-algorithm.html">
Catalan Number Algorithm
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/37.fb96070b.js" defer></script>
</body>
</html>