dijkstra.py:
import yaml
import copy
class Dijkstra:
def __init__(self, path, start_node):
self.data = self.config_reader(path)
self.start_node = start_node
self.node_data = self.node_data_init()
def config_reader(self, path):
with open(path, 'r', encoding='utf8') as f:
return yaml.load(f, yaml.BaseLoader)
def get_shortest_path(self, node_value, visited_path=[], path=[], base_cost=0):
for n, v in node_value.items():
v = int(v)
_visited_path = copy.deepcopy(visited_path)
_path = copy.deepcopy(path)
print(self.data[n], _visited_path, path, n, v)
if n not in _visited_path:
_visited_path.append(n)
if v == 0:
continue
else:
_path.append(n)
if base_cost+v < self.node_data[n]['cost']:
self.node_data[n]['cost'] = base_cost + v
self.node_data[n]['path'] = _path
self.get_shortest_path(self.data[n], _visited_path, _path, base_cost+v)
def node_data_init(self):
node_data = {}
for n in self.data.keys():
node_data.update({
n: {
'cost': float('inf'),
'path': []
}
})
return node_data
def run(self):
visited_path = path = [self.start_node]
self.node_data[self.start_node]['cost'] = 0
self.node_data[self.start_node]['path'] = path
self.get_shortest_path(self.data[self.start_node], path, visited_path)
print(self.data)
print(self.node_data)
if __name__ == '__main__':
dj = Dijkstra('dj.yaml', 's2')
dj.run()
dj.yaml:
s0:
s0: 0
s1: 2
s2: 6
s1:
s0: 2
s1: 0
s3: 5
s2:
s0: 6
s2: 0
s3: 8
s3:
s3: 0
s1: 5
s2: 8
s4: 10
s5: 15
s4:
s4: 0
s3: 10
s5: 6
s6: 2
s5:
s5: 0
s3: 15
s4: 6
s6: 6
s6:
s6: 0
s4: 2
s5: 6
s7: 1
s7:
s6: 1
s7: 0
s8:
s8: 0