added floyd algo

eloyekunle · eloyekunle · commit 1827cf2b1e30 · 2018-09-18T19:52:01.000+01:00
diff --git a/hackerrank/data/floyd-city-of-blinding-lights-001.sol.txt b/hackerrank/data/floyd-city-of-blinding-lights-001.sol.txt
@@ -0,0 +1,3 @@
+5
+-1
+11
diff --git a/hackerrank/data/floyd-city-of-blinding-lights-001.txt b/hackerrank/data/floyd-city-of-blinding-lights-001.txt
@@ -0,0 +1,10 @@
+4 5
+1 2 5
+1 4 24
+2 4 6
+3 4 4
+3 2 7
+3
+1 2
+3 1
+1 4
diff --git a/hackerrank/graphs/floyd-city-of-blinding-lights.py b/hackerrank/graphs/floyd-city-of-blinding-lights.py
@@ -0,0 +1,55 @@
+#!/bin/python3
+
+import math
+import os
+import random
+import re
+import sys
+
+def floyd_warshall(m):
+    n = len(m)
+
+    for k in range(n):
+        kk = m[k]
+        for i in range(n):
+            ii = m[i]
+            ik = ii[k]
+            if ik == math.inf:
+                continue
+            for j in range(n):
+                kj = kk[j]
+                if kj == math.inf:
+                    continue
+                m[i][j] = min(ii[j], ik + kj)
+
+    return m
+
+if __name__ == '__main__':
+    f = open('../data/floyd-city-of-blinding-lights-001.txt')
+
+    n, m = map(int, f.readline().split())
+
+    g_matrix = [[math.inf] * n for _ in range(n)]
+
+    for _ in range(m):
+        u,v,w = map(int, f.readline().rstrip().split())
+        g_matrix[u-1][v-1] = w
+
+    for i in range(n):
+        g_matrix[i][i] = 0
+
+    apsp = floyd_warshall(g_matrix)
+
+    q = int(f.readline())
+
+    for q_itr in range(q):
+        xy = f.readline().split()
+
+        x = int(xy[0])
+
+        y = int(xy[1])
+
+        if not apsp[x-1][y-1] == math.inf:
+            print(apsp[x-1][y-1])
+        else:
+            print(-1)

-Original file line number
+Diff line change
@@ @@ -0,0 +1,10 @@ @@
 +4 5
 +1 2 5
 +1 4 24
 +2 4 6
 +3 4 4
 +3 2 7
 +3
 +1 2
 +3 1
 +1 4