Created
November 21, 2015 04:36
-
-
Save mdsrosa/c71339cb23bc51e711d8 to your computer and use it in GitHub Desktop.
Modified Python implementation of Dijkstra's Algorithm (https://gist.github.com/econchick/4666413)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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']) |
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hello,
In this code, Why I should revise the add_edge definition in Graph class like this: