-
Notifications
You must be signed in to change notification settings - Fork 0
/
romanian_dfs.py
110 lines (93 loc) · 2.61 KB
/
romanian_dfs.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
import numpy as np
class Edge():
total_instances = 0
instances = []
def __init__(self, src, dest, weight):
self.src = src
self.dest = dest
self.weight = weight
# Initialize instance-specific variables
self.instance_total = 0
self.instance_list = []
# Increment the class variable for total instances
Edge.total_instances += 1
# Increment the instance-specific variable for total instances
self.instance_total += 1
# Append the instance to the class variable instances list
Edge.instances.append(self)
# Append the instance to the instance-specific instances list
self.instance_list.append(self)
vertex = 5
matrix = np.zeros((vertex+1,vertex+1))
edge1 = Edge(1, 4, 2)
edge2 = Edge(2, 5, 8)
edge3 = Edge(3, 1, 10)
edge4 = Edge(3, 4, 5)
edge5 = Edge(3, 5, 6)
edge6 = Edge(4, 2, 15)
for instance in Edge.instances:
start = instance.src
end = instance.dest
weight = instance.weight
matrix[start][end] = weight
for i in range(1, vertex+1):
for j in range(1, vertex+1):
if matrix[i][j] != 0:
print(f"[{i}, {j}]: {matrix[i][j]}")
edges = [
['A', 'B', 10],
['A', 'C', 5],
['C', 'B', 3],
['B', 'D', 1],
['C', 'D', 9],
['C', 'E', 2],
['E', 'D', 6],
['E', 'A', 2]
]
graph1 = {}
graph1['A'] = [
{'neighbor': 'B', 'dist' : 10},
{'neighbor' : 'C', 'dist' : 5}
]
graph1['C'] = [
{'neighbor': 'B', 'dist' : 3},
{'neighbor' : 'D', 'dist' : 9},
{'neighbor' : 'E', 'dist': 2}
]
graph1['B'] = [
{'neighbor' : 'D', 'dist': 1}
]
graph1['E'] = [
{'neighbor' : 'D', 'dist': 6},
{'neighbor' : 'A', 'dist': 2}
]
graph1['D'] = [
{'neighbor' : None, 'dist': None}
]
cost = {}
cost['A'] = float('inf')
cost['B'] = float('inf')
cost['C'] = float('inf')
cost['D'] = float('inf')
cost['E'] = float('inf')
nodes = []
for i, edge in enumerate(edges):
for j, node in enumerate(edge[:2]):
if node not in nodes:
nodes.append(node)
total_cost = 0
visited = []
neighbors = []
shortest_neighbor = None
def shortest_path(graph, src, dest):
for i, neighbor in enumerate(graph[src]):
neighbors.append(neighbor['neighbor'])
cost = total_cost + neighbor['dist']
total_cost = total_cost + cost[neighbor['neighbor']]
for i, neighbor in enumerate(graph[src]):
if shortest_neighbor:
if cost[neighbor] < shortest_neighbor['cost']:
shortest_neighbor = neighbor['neighbor']
else:
shortest_neighbor = neighbor['neighbor']
visited.append(src)