-
Notifications
You must be signed in to change notification settings - Fork 0
/
johnsonsAlgorithm.py
145 lines (94 loc) · 3.56 KB
/
johnsonsAlgorithm.py
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
"""Code for the implementation of Johnson's Algorithm"""
# Importing dependencies
import numpy as np
import math
import visualizeDijkstra as vd
def ExtractMin(Q, mainTable):
"""Gives vertex in Q (Unvisited Set) minimum distance value"""
minD = math.inf
minE = None
for i in Q:
if mainTable[i][0] < minD:
minD = mainTable[i][0]
minE = i
return minE
def adj(u, AdjMatrix):
"""Gives elements adjacent to current vertex"""
AdjList = []
for i in range(0, len(AdjMatrix[u])):
if AdjMatrix[u][i] >= 0:
AdjList.append(i)
return AdjList
def Dijkstra(graph, source):
"""Code for implementing Dijkstra's Algorithm"""
# Storing number of vertices
numVertices = len(graph)
# Table to store computed vertices
mainTable = []
Q = set()
for v in range(0, numVertices):
mTow = []
Q.add(v)
# Storing distance
mTow.append(math.inf)
# Parent
mTow.append(None)
# Adding the entity to Dijkstra's table
mainTable.append(mTow)
# Setting of source
mainTable[source][0] = 0
mainTable[source][1] = None
# Repeating till visited set is empty
while len(Q) != 0:
u = ExtractMin(Q, mainTable)
if u == None:
break
Q.remove(u)
for v in adj(u, graph):
if v in Q and mainTable[v][0] > mainTable[u][0] + graph[u, v]:
mainTable[v][0] = mainTable[u][0] + graph[u, v]
mainTable[v][1] = u
# Returning the table to after graph Dijkstras ran sucessfully
# returning mainTable
return mainTable
def BellmanFord(edges, graph):
"""Code for running Bellman-Ford"""
# To get number of vertices
num = len(graph)
# Initializing a distance list
dist = [math.inf] * (num + 1)
# Distance from source to source will always be zero
dist[num] = 0
# Inserting edges from imaginary source to vertices in edge list
for i in range(num):
edges.append([num, i, 0])
# Running Bellmanford loop, number of vertices - 1 times
for i in range(num):
for (source, destination, weight) in edges:
if (dist[source] != math.inf) and (dist[source] + weight < dist[destination]):
dist[destination] = dist[source] + weight
# Returning reweighted graph
return dist[0:num]
def Johnson(graph):
"""Code for running Johnson's"""
# Creating an empty list to store non-zero edges
edges = []
# Creating a list of non-zero edges to be sent to Bellmanford to be reweighted
for i in range(len(graph)):
for j in range(len(graph[i])):
if graph[i, j] != 0:
edges.append([i, j, graph[i, j]])
# Modified weights returned by Bellmanford method
reweightFactor = BellmanFord(edges, graph)
# Creating an adjacency matrix with all entries as zero
newGraph = np.zeros([len(graph), len(graph)])
for i in range(len(graph)):
for j in range(len(graph)):
if graph[i, j] != 0:
newGraph[i, j] = graph[i, j] + reweightFactor[i] - reweightFactor[j]
# Non-negative weighted graph output
#print("New Graph : ", newGraph)
# Running Djiktras Algorithm by taking each of the vertices as source vertex
for source in range(len(graph)):
# Displaying method
vd.convert(Dijkstra(newGraph, source),source)