-
Notifications
You must be signed in to change notification settings - Fork 2
/
Floyd Warshall algorithm.swift
37 lines (37 loc) · 1.43 KB
/
Floyd Warshall algorithm.swift
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
public let vertices = 4
public let INF = 99999
func floydWarshall(graph: [[Int]]) {
var distanceBetweenVertices = Array(repeating: Array(repeating: 0,count: vertices), count: vertices)
for eachRow in 0..<vertices {
for eachColumn in 0..<vertices {
distanceBetweenVertices[eachRow][eachColumn] = graph[eachRow][eachColumn]
}
}
for freezingRowAndColumn in 0..<vertices {
for eachRow in 0..<vertices {
for eachColumn in 0..<vertices {
distanceBetweenVertices[eachRow][eachColumn] = min(distanceBetweenVertices[eachRow][eachColumn], (distanceBetweenVertices[eachRow][freezingRowAndColumn] + distanceBetweenVertices[freezingRowAndColumn][eachColumn]))
}
}
}
printTheShortestDistances(distance: distanceBetweenVertices)
}
func printTheShortestDistances(distance: [[Int]]) {
print("Following matrix shows the shortest paths between every pair of vertices")
for eachRow in 0..<vertices {
for eachColumn in 0..<vertices {
if distance[eachRow][eachColumn] == INF {
print("INF",terminator: " ")
}
else {
print(distance[eachRow][eachColumn],terminator: " ")
}
}
print(" ")
}
}
let graph = [[0, 3, INF, 5],
[2, 0, INF, 4],
[INF, 1, 0, INF],
[INF, INF, 2, 0]]
floydWarshall(graph : graph)