-
-
Save mdsrosa/c71339cb23bc51e711d8 to your computer and use it in GitHub Desktop.
from collections import defaultdict, deque | |
class Graph(object): | |
def __init__(self): | |
self.nodes = set() | |
self.edges = defaultdict(list) | |
self.distances = {} | |
def add_node(self, value): | |
self.nodes.add(value) | |
def add_edge(self, from_node, to_node, distance): | |
self.edges[from_node].append(to_node) | |
self.edges[to_node].append(from_node) | |
self.distances[(from_node, to_node)] = distance | |
def dijkstra(graph, initial): | |
visited = {initial: 0} | |
path = {} | |
nodes = set(graph.nodes) | |
while nodes: | |
min_node = None | |
for node in nodes: | |
if node in visited: | |
if min_node is None: | |
min_node = node | |
elif visited[node] < visited[min_node]: | |
min_node = node | |
if min_node is None: | |
break | |
nodes.remove(min_node) | |
current_weight = visited[min_node] | |
for edge in graph.edges[min_node]: | |
try: | |
weight = current_weight + graph.distances[(min_node, edge)] | |
except: | |
continue | |
if edge not in visited or weight < visited[edge]: | |
visited[edge] = weight | |
path[edge] = min_node | |
return visited, path | |
def shortest_path(graph, origin, destination): | |
visited, paths = dijkstra(graph, origin) | |
full_path = deque() | |
_destination = paths[destination] | |
while _destination != origin: | |
full_path.appendleft(_destination) | |
_destination = paths[_destination] | |
full_path.appendleft(origin) | |
full_path.append(destination) | |
return visited[destination], list(full_path) | |
if __name__ == '__main__': | |
graph = Graph() | |
for node in ['A', 'B', 'C', 'D', 'E', 'F', 'G']: | |
graph.add_node(node) | |
graph.add_edge('A', 'B', 10) | |
graph.add_edge('A', 'C', 20) | |
graph.add_edge('B', 'D', 15) | |
graph.add_edge('C', 'D', 30) | |
graph.add_edge('B', 'E', 50) | |
graph.add_edge('D', 'E', 30) | |
graph.add_edge('E', 'F', 5) | |
graph.add_edge('F', 'G', 2) | |
print(shortest_path(graph, 'A', 'D')) # output: (25, ['A', 'B', 'D']) |
@mdsrosa
Hi!
Thanks Alot for this implementation!
Q:
If I will remove line 15: self.edges[to_node].append(from_node)
Will it make the graph DIRECTED instead of undirected? Will it work?
I did not fully understand how line 16:
self.distances[(from_node, to_node)] = distance
works for both edges.
Just want to tell you, THANK YOU!!!! I have spent weeks on this, my assignment was like super late but thank you, I was able to bend my data structure to your classes will! Appreciate it
THIS IS NEAT!
BUT WHAT IF THERE EXIST TWO shortest paths, HOW CAN I GET BOTH? THANKS.
Thank you so, so, very much! I spent hours banging my head against a wall working with recursive functions before I found this Gist, which works like a charm!
Works like a charm. Thanks a bunch.
EdgeList can contain duplicate items in current scenario. It would be great if it is a defautdict(set)
. Would there be any improvement in performance?
this is o(mn) naive implementation correct?
Hello,
In this code, Why I should revise the add_edge definition in Graph class like this:
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
self.distances[(to_node, from_node)] = distance #I added this line
It doesn't work when the destination is the same as the origin.
I added few modifications for when I need to calculate the distance for same node:
` def are_these_nodes_adjacents(from_node, to_node):
return to_node in graph.edges[from_node]
def shortest_path_same_node(graph, origin, visited):
min_distance = None
min_node = None
for node, distance in visited.items():
if(are_these_nodes_adjacents(node, origin)):
if(min_node is None):
min_node = node
min_distance = distance + graph.distances[(min_node, origin)]
else:
if(min_distance > distance):
min_node = node
min_distance = distance + graph.distances[(min_node, origin)]
return min_distance
def shortest_path2(graph, origin, destination):
visited, paths = dijkstra(graph, origin)
result = 0
if(origin == destination):
result = shortest_path_same_node(graph, origin, visited)
else:
result = visited[destination]
return result`
Thanks this is great.
Hi can I get a quest? How can I replace first line? I just started my way with python so don't judge me ;)
I want replace that because I don't know how it works but I want to implement this algorithm
Amazing Graph class! Thanks a lot!