Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Python implementation of Dijkstra's Algorithm
class Graph:
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 dijsktra(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]:
weight = current_weight + graph.distance[(min_node, edge)]
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge] = min_node
return visited, path
@vincentarelbundock

This comment has been minimized.

Show comment
Hide comment
@vincentarelbundock

vincentarelbundock Dec 4, 2013

I was looking for this. Thanks! Very nice nice and clean!

I was looking for this. Thanks! Very nice nice and clean!

@dlumma

This comment has been minimized.

Show comment
Hide comment
@dlumma

dlumma Feb 27, 2014

Thanks for this! I tried running it and ran into a typo.

Line 38: typo in distance should be distances

dlumma commented Feb 27, 2014

Thanks for this! I tried running it and ran into a typo.

Line 38: typo in distance should be distances

@shahkomal

This comment has been minimized.

Show comment
Hide comment
@shahkomal

shahkomal Mar 20, 2014

I am not able to understand what to pass in the second argument (initial) for dijsktra function. Can anyone please help me?

I am not able to understand what to pass in the second argument (initial) for dijsktra function. Can anyone please help me?

@rahanar

This comment has been minimized.

Show comment
Hide comment
@benaxelrod

This comment has been minimized.

Show comment
Hide comment
@benaxelrod

benaxelrod Jun 9, 2014

I think you also need:

 self.distances[(to_node, from_node)] = distance

at line 14. Or else the algorithm won't know the distance from nodes A to B is the same as from B to A.

I think you also need:

 self.distances[(to_node, from_node)] = distance

at line 14. Or else the algorithm won't know the distance from nodes A to B is the same as from B to A.

@bizzk3t

This comment has been minimized.

Show comment
Hide comment
@bizzk3t

bizzk3t Jun 23, 2014

benaxelrod, I believe if you add that line, it will make the graph undirected rather than directed

bizzk3t commented Jun 23, 2014

benaxelrod, I believe if you add that line, it will make the graph undirected rather than directed

@joyrexus

This comment has been minimized.

Show comment
Hide comment
@joyrexus

joyrexus Jun 28, 2014

Note the running time for this implementation is going to be O(mn) where n is the number of vertices and m is the number of edges. FWIW, implementations that utilize a priority queue can run in O(m log n) time.

Note the running time for this implementation is going to be O(mn) where n is the number of vertices and m is the number of edges. FWIW, implementations that utilize a priority queue can run in O(m log n) time.

@57uff3r

This comment has been minimized.

Show comment
Hide comment
@57uff3r

57uff3r Oct 13, 2014

I also added try-catch block in loop with edges: https://gist.github.com/57uff3r/99b4064cbbcbf6a73963

57uff3r commented Oct 13, 2014

I also added try-catch block in loop with edges: https://gist.github.com/57uff3r/99b4064cbbcbf6a73963

@ross-kruse

This comment has been minimized.

Show comment
Hide comment
@ross-kruse

ross-kruse Apr 11, 2015

How do I interpret the output?

How do I interpret the output?

@mdsrosa

This comment has been minimized.

Show comment
Hide comment
@mdsrosa

mdsrosa Nov 21, 2015

@econchick Thank you very much for sharing this implementation. 😄
@rokruse I've added a function that shows that result in a very nice way to interpret it: https://gist.github.com/mdsrosa/c71339cb23bc51e711d8

mdsrosa commented Nov 21, 2015

@econchick Thank you very much for sharing this implementation. 😄
@rokruse I've added a function that shows that result in a very nice way to interpret it: https://gist.github.com/mdsrosa/c71339cb23bc51e711d8

@zaz

This comment has been minimized.

Show comment
Hide comment
@zaz

zaz Dec 15, 2015

A lot of the first half of the loop can be cleaned up using set.intersection() and min(). It also seems like you could do with some functions to actually find the path:

zaz / dijkstra.py

zaz commented Dec 15, 2015

A lot of the first half of the loop can be cleaned up using set.intersection() and min(). It also seems like you could do with some functions to actually find the path:

zaz / dijkstra.py

@SHIMONSHEIBA

This comment has been minimized.

Show comment
Hide comment
@SHIMONSHEIBA

SHIMONSHEIBA Dec 25, 2015

@econchick
Could I modify this implementation to a DIRECTED graph by deleting row 12:
self.edges[to_node].append(from_node)
Will it work?
@joyrexus could you please give another link that works?

@econchick
Could I modify this implementation to a DIRECTED graph by deleting row 12:
self.edges[to_node].append(from_node)
Will it work?
@joyrexus could you please give another link that works?

@TejazTj

This comment has been minimized.

Show comment
Hide comment
@TejazTj

TejazTj Feb 7, 2016

but i have a different code...can u help me solve it..??

screen shot 2016-02-07 at 2 47 33 pm
screen shot 2016-02-07 at 2 47 52 pm
screen shot 2016-02-07 at 2 48 07 pm

TejazTj commented Feb 7, 2016

but i have a different code...can u help me solve it..??

screen shot 2016-02-07 at 2 47 33 pm
screen shot 2016-02-07 at 2 47 52 pm
screen shot 2016-02-07 at 2 48 07 pm

@KanwarGill

This comment has been minimized.

Show comment
Hide comment
@KanwarGill

KanwarGill Feb 8, 2016

This was very useful. Thank you!

This was very useful. Thank you!

@jzohrab

This comment has been minimized.

Show comment
Hide comment
@jzohrab

jzohrab Mar 31, 2016

I don't believe the gist's implementation is correct, at least it doesn't work on a simple use case unless I've misused it. I have a simple ring, a -> b, a -> c, b -> c with weights. The algorithm doesn't give distances to b or c, even with the try-catch block from 57uff3r.

import dj

g = dj.Graph()
g.add_node('a')
g.add_node('b')
g.add_node('c')

g.add_edge('a', 'b', 10)
g.add_edge('b', 'c', 10)
g.add_edge('a', 'c', 15)

print dj.dijsktra(g, 'a')

# returns ({'a': 0}, {})

jzohrab commented Mar 31, 2016

I don't believe the gist's implementation is correct, at least it doesn't work on a simple use case unless I've misused it. I have a simple ring, a -> b, a -> c, b -> c with weights. The algorithm doesn't give distances to b or c, even with the try-catch block from 57uff3r.

import dj

g = dj.Graph()
g.add_node('a')
g.add_node('b')
g.add_node('c')

g.add_edge('a', 'b', 10)
g.add_edge('b', 'c', 10)
g.add_edge('a', 'c', 15)

print dj.dijsktra(g, 'a')

# returns ({'a': 0}, {})
@MagallanesFito

This comment has been minimized.

Show comment
Hide comment
@MagallanesFito

MagallanesFito Jun 12, 2016

Nice code, clear and great. Thank you

Nice code, clear and great. Thank you

@MagallanesFito

This comment has been minimized.

Show comment
Hide comment
@MagallanesFito

MagallanesFito Jun 12, 2016

Nice code, clear and great. Thank you

Nice code, clear and great. Thank you

@jazcap53

This comment has been minimized.

Show comment
Hide comment
@jazcap53

jazcap53 Jun 29, 2016

Thanks very much for this. Clean, clear -- taught me a lot!

Thanks very much for this. Clean, clear -- taught me a lot!

@rockyzhengwu

This comment has been minimized.

Show comment
Hide comment
@rockyzhengwu

rockyzhengwu Aug 6, 2016

delete
self.edges[to_node].append(from_node) row 12
because the graph directed.

delete
self.edges[to_node].append(from_node) row 12
because the graph directed.

@freegyp

This comment has been minimized.

Show comment
Hide comment
@freegyp

freegyp Sep 10, 2016

If I'm right, in this implementation, finding min_node takes O(n) time (n is the number of nodes).

freegyp commented Sep 10, 2016

If I'm right, in this implementation, finding min_node takes O(n) time (n is the number of nodes).

@alexhwoods

This comment has been minimized.

Show comment
Hide comment
@alexhwoods

alexhwoods Sep 26, 2016

Agree with rockyzhengwu, it's a directed, weighted graph.

Great implementation!

Agree with rockyzhengwu, it's a directed, weighted graph.

Great implementation!

@arganoid

This comment has been minimized.

Show comment
Hide comment
@arganoid

arganoid Nov 16, 2016

`
g = Graph()
g.add_node('a')
g.add_node('b')
g.add_node('c')
g.add_node('d')

g.add_edge('a', 'b', 10)
g.add_edge('b', 'c', 10)
g.add_edge('a', 'c', 15)
g.add_edge('c', 'd', 20)

print(dijsktra(g, 'a'))
`

Output is:
({'a': 0, 'c': 15, 'b': 10}, {'c': 'a', 'b': 'a'})

What happened to d?

arganoid commented Nov 16, 2016

`
g = Graph()
g.add_node('a')
g.add_node('b')
g.add_node('c')
g.add_node('d')

g.add_edge('a', 'b', 10)
g.add_edge('b', 'c', 10)
g.add_edge('a', 'c', 15)
g.add_edge('c', 'd', 20)

print(dijsktra(g, 'a'))
`

Output is:
({'a': 0, 'c': 15, 'b': 10}, {'c': 'a', 'b': 'a'})

What happened to d?

@zirons1

This comment has been minimized.

Show comment
Hide comment
@zirons1

zirons1 Dec 6, 2016

You spelled Dijkstra wrong in the function definition -_-

zirons1 commented Dec 6, 2016

You spelled Dijkstra wrong in the function definition -_-

@eyzuky

This comment has been minimized.

Show comment
Hide comment
@eyzuky

eyzuky Dec 17, 2016

I have a silly question - where do I specify my target node?

eyzuky commented Dec 17, 2016

I have a silly question - where do I specify my target node?

@manliu1225

This comment has been minimized.

Show comment
Hide comment
@manliu1225

manliu1225 Feb 17, 2017

thank you. this is very useful for me.

thank you. this is very useful for me.

@maskani-moh

This comment has been minimized.

Show comment
Hide comment
@maskani-moh

maskani-moh Feb 20, 2017

Great code. Thank you!

Great code. Thank you!

@elvaigh

This comment has been minimized.

Show comment
Hide comment
@elvaigh

elvaigh Mar 4, 2017

few mistake in line 38 : "weight = current_weight + graph.distance[(min_node, edge)] "
==> weight = current_weight + graph.distances[(min_node, edge)]
Thanks very usefull!

elvaigh commented Mar 4, 2017

few mistake in line 38 : "weight = current_weight + graph.distance[(min_node, edge)] "
==> weight = current_weight + graph.distances[(min_node, edge)]
Thanks very usefull!

@kyle-sorensen

This comment has been minimized.

Show comment
Hide comment
@kyle-sorensen

kyle-sorensen Mar 16, 2017

I can't speak for Python 3 but in 2.7 you need:

from collections import defaultdict

I can't speak for Python 3 but in 2.7 you need:

from collections import defaultdict

@danielgaza

This comment has been minimized.

Show comment
Hide comment
@danielgaza

danielgaza May 2, 2017

Hello Dears
I have a question regarding the short path Dijkstra,
I read the algorithm, but I do not know how to apply it on my graph.
I have a graph network composed of 11 points, and the points coordinates are as follow:

A(2,9)
B(1,6)
C(5,3)
D(4,7)
E(6,8)
F(6,6)
G(8,5)
H(12,4)
I(12,7)
J(10,9)
K(8,7)

and the points are connected together by 23 lines as follow:

  1. AB
  2. BC
  3. BD
  4. AD
  5. DC
  6. AE
  7. DE
  8. DF
  9. CF
  10. EF
  11. CG
  12. FG
  13. FK
  14. EK
  15. KG
  16. CH
  17. GH
  18. GI
  19. KI
  20. IH
  21. EJ
  22. KJ
  23. IJ

How I can find the shortest path between point A and point H using the above explained defined function ?

Please help me.

Thanks in advance

Hello Dears
I have a question regarding the short path Dijkstra,
I read the algorithm, but I do not know how to apply it on my graph.
I have a graph network composed of 11 points, and the points coordinates are as follow:

A(2,9)
B(1,6)
C(5,3)
D(4,7)
E(6,8)
F(6,6)
G(8,5)
H(12,4)
I(12,7)
J(10,9)
K(8,7)

and the points are connected together by 23 lines as follow:

  1. AB
  2. BC
  3. BD
  4. AD
  5. DC
  6. AE
  7. DE
  8. DF
  9. CF
  10. EF
  11. CG
  12. FG
  13. FK
  14. EK
  15. KG
  16. CH
  17. GH
  18. GI
  19. KI
  20. IH
  21. EJ
  22. KJ
  23. IJ

How I can find the shortest path between point A and point H using the above explained defined function ?

Please help me.

Thanks in advance

@ngocqd

This comment has been minimized.

Show comment
Hide comment
@ngocqd

ngocqd May 15, 2017

when i run code in pycharm, i got the error
TypeError: '<' not supported between instances of 'Vertex' and 'Vertex'

ngocqd commented May 15, 2017

when i run code in pycharm, i got the error
TypeError: '<' not supported between instances of 'Vertex' and 'Vertex'

@Rajdeep400

This comment has been minimized.

Show comment
Hide comment
@Rajdeep400

Rajdeep400 May 31, 2017

with due respect to econchick, thanks to your submitted code, but people you can use this code of mine, I just simply fixed some bugs of the code above, and also path is displayed here;
it is also a directed graph, NO ERROR.
All credit to econchick.
Fixed by : ME

from collections import defaultdict
class Graph:
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.distances[(from_node, to_node)] = distance

def dijkstra(graph, initial):
visited = {initial: 0}
path = defaultdict(list)

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]:
        weight = current_weight + graph.distances[(min_node, edge)]
        if edge not in visited or weight < visited[edge]:
            visited[edge] = weight
            path[edge].append(min_node)

return path

g = Graph()

g.add_node('A')
g.add_node('B')
g.add_node('C')
g.add_node('D')
g.add_node('E')
g.add_node('F')
g.add_node('G')

g.add_edge('A','B',12)
g.add_edge('A','C',7)
g.add_edge('B','D',1)
g.add_edge('B','A',12)
g.add_edge('D','E',8)
g.add_edge('C','F',3)
g.add_edge('D','G',5)
g.add_edge('F','B',1)
g.add_edge('F','G',2)
g.add_edge('C','D',13)
g.add_edge('E','B',6)

print(dijkstra(g, 'A')['B'])

Rajdeep400 commented May 31, 2017

with due respect to econchick, thanks to your submitted code, but people you can use this code of mine, I just simply fixed some bugs of the code above, and also path is displayed here;
it is also a directed graph, NO ERROR.
All credit to econchick.
Fixed by : ME

from collections import defaultdict
class Graph:
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.distances[(from_node, to_node)] = distance

def dijkstra(graph, initial):
visited = {initial: 0}
path = defaultdict(list)

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]:
        weight = current_weight + graph.distances[(min_node, edge)]
        if edge not in visited or weight < visited[edge]:
            visited[edge] = weight
            path[edge].append(min_node)

return path

g = Graph()

g.add_node('A')
g.add_node('B')
g.add_node('C')
g.add_node('D')
g.add_node('E')
g.add_node('F')
g.add_node('G')

g.add_edge('A','B',12)
g.add_edge('A','C',7)
g.add_edge('B','D',1)
g.add_edge('B','A',12)
g.add_edge('D','E',8)
g.add_edge('C','F',3)
g.add_edge('D','G',5)
g.add_edge('F','B',1)
g.add_edge('F','G',2)
g.add_edge('C','D',13)
g.add_edge('E','B',6)

print(dijkstra(g, 'A')['B'])

@manoelstilpen

This comment has been minimized.

Show comment
Hide comment
@manoelstilpen

manoelstilpen Jun 9, 2017

You should add in the function add_edge the command self.distances[(to_node, from_node)] = distance

You should add in the function add_edge the command self.distances[(to_node, from_node)] = distance

@abelevtsov

This comment has been minimized.

Show comment
Hide comment
@abelevtsov

abelevtsov Jul 15, 2017

please fix
weight = current_weight + graph.distance[(min_node, edge)]
to
weight = current_weight + graph.distances[(min_node, edge)]
(distance -> distances)

please fix
weight = current_weight + graph.distance[(min_node, edge)]
to
weight = current_weight + graph.distances[(min_node, edge)]
(distance -> distances)

@esarabdikar

This comment has been minimized.

Show comment
Hide comment
@esarabdikar

esarabdikar Aug 3, 2017

hey, can I implement this dijkstra code on mobile robot ?
I use simulator mobile robot "pysimiam" which is python version of matlab's sim.i.am.

hey, can I implement this dijkstra code on mobile robot ?
I use simulator mobile robot "pysimiam" which is python version of matlab's sim.i.am.

@tatianass

This comment has been minimized.

Show comment
Hide comment
@tatianass

tatianass Dec 14, 2017

It doesn't work when the destination is the same as the origin.

It doesn't work when the destination is the same as the origin.

@MaximusWudy

This comment has been minimized.

Show comment
Hide comment
@MaximusWudy

MaximusWudy Jan 13, 2018

Here is a complete version of Python2.7 code regarding the problematic original version. Just paste in in any .py file and run.
Output: The storage objects are pretty clear; dijkstra algorithm returns with first dict of shortest distance from source_node to {target_node: distance length} and second dict of the predecessor of each node, i.e. {2:1} means the predecessor for node 2 is 1 --> we then are able to reverse the process and obtain the path from source node to every other node.

For example, we have {5:2} and {2:1}, which renders that the path from source node 1 to 5 is 1-->2-->5.

from collections import defaultdict
class Graph:
def init(self):
self.nodes = set() # set object
self.edges = defaultdict(list)
self.distances = {}

def add_nodes(self, value):
    for i in value:
        self.nodes.add(i) # add element into set
    
def add_edge(self, from_node, to_node, distance):
    self.edges[from_node].append(to_node)
    self.edges[to_node].append(from_node) # dict to neighbour nodes
    self.distances[(from_node, to_node)] = distance # dict for distance
    self.distances[(to_node, from_node)] = distance

def dijsktra(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]:
        weight = current_weight + graph.distances[(min_node, edge)]
        if edge not in visited or weight < visited[edge]:
            visited[edge] = weight
            path[edge] = min_node

return visited, path

g = Graph()
g.add_nodes([i+1 for i in range(8)])
g.add_edge(1, 2, 4)
g.add_edge(1, 3, 1)
g.add_edge(2, 4, 3)
g.add_edge(2, 5, 7)
g.add_edge(4, 8, 3)
g.add_edge(5, 8, 4)
g.add_edge(3, 6, 3)
g.add_edge(3, 7, 2)
g.add_edge(6, 7, 1)
print "nodes:", g.nodes
print "edges:", g.edges
print "distances: ", g.distances

----------

print "-" * 25
source_node = 1
print "Source node:", source_node
print dijsktra(g, 1) # return with visited and path

And the return output should be :
nodes: set([1, 2, 3, 4, 5, 6, 7, 8])
edges: defaultdict(<type 'list'>, {1: [2, 3], 2: [1, 4, 5], 3: [1, 6, 7], 4: [2, 8], 5: [2, 8], 6: [3, 7], 7: [3, 6], 8: [4, 5]})
distances: {(1, 2): 4, (7, 3): 2, (1, 3): 1, (6, 7): 1, (4, 8): 3, (8, 5): 4, (7, 6): 1, (3, 1): 1, (2, 1): 4, (6, 3): 3, (3, 6): 3, (3, 7): 2, (4, 2): 3, (2, 5): 7, (5, 2): 7, (2, 4): 3, (5, 8): 4, (8, 4): 3}

Source node: 1
({1: 0, 2: 4, 3: 1, 4: 7, 5: 11, 6: 4, 7: 3, 8: 10}, {2: 1, 3: 1, 4: 2, 5: 2, 6: 3, 7: 3, 8: 4})

MaximusWudy commented Jan 13, 2018

Here is a complete version of Python2.7 code regarding the problematic original version. Just paste in in any .py file and run.
Output: The storage objects are pretty clear; dijkstra algorithm returns with first dict of shortest distance from source_node to {target_node: distance length} and second dict of the predecessor of each node, i.e. {2:1} means the predecessor for node 2 is 1 --> we then are able to reverse the process and obtain the path from source node to every other node.

For example, we have {5:2} and {2:1}, which renders that the path from source node 1 to 5 is 1-->2-->5.

from collections import defaultdict
class Graph:
def init(self):
self.nodes = set() # set object
self.edges = defaultdict(list)
self.distances = {}

def add_nodes(self, value):
    for i in value:
        self.nodes.add(i) # add element into set
    
def add_edge(self, from_node, to_node, distance):
    self.edges[from_node].append(to_node)
    self.edges[to_node].append(from_node) # dict to neighbour nodes
    self.distances[(from_node, to_node)] = distance # dict for distance
    self.distances[(to_node, from_node)] = distance

def dijsktra(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]:
        weight = current_weight + graph.distances[(min_node, edge)]
        if edge not in visited or weight < visited[edge]:
            visited[edge] = weight
            path[edge] = min_node

return visited, path

g = Graph()
g.add_nodes([i+1 for i in range(8)])
g.add_edge(1, 2, 4)
g.add_edge(1, 3, 1)
g.add_edge(2, 4, 3)
g.add_edge(2, 5, 7)
g.add_edge(4, 8, 3)
g.add_edge(5, 8, 4)
g.add_edge(3, 6, 3)
g.add_edge(3, 7, 2)
g.add_edge(6, 7, 1)
print "nodes:", g.nodes
print "edges:", g.edges
print "distances: ", g.distances

----------

print "-" * 25
source_node = 1
print "Source node:", source_node
print dijsktra(g, 1) # return with visited and path

And the return output should be :
nodes: set([1, 2, 3, 4, 5, 6, 7, 8])
edges: defaultdict(<type 'list'>, {1: [2, 3], 2: [1, 4, 5], 3: [1, 6, 7], 4: [2, 8], 5: [2, 8], 6: [3, 7], 7: [3, 6], 8: [4, 5]})
distances: {(1, 2): 4, (7, 3): 2, (1, 3): 1, (6, 7): 1, (4, 8): 3, (8, 5): 4, (7, 6): 1, (3, 1): 1, (2, 1): 4, (6, 3): 3, (3, 6): 3, (3, 7): 2, (4, 2): 3, (2, 5): 7, (5, 2): 7, (2, 4): 3, (5, 8): 4, (8, 4): 3}

Source node: 1
({1: 0, 2: 4, 3: 1, 4: 7, 5: 11, 6: 4, 7: 3, 8: 10}, {2: 1, 3: 1, 4: 2, 5: 2, 6: 3, 7: 3, 8: 4})

@bp8017

This comment has been minimized.

Show comment
Hide comment
@bp8017

bp8017 Feb 3, 2018

I am looking for an "opposite" of this. Something that finds the longest path between vertices.

bp8017 commented Feb 3, 2018

I am looking for an "opposite" of this. Something that finds the longest path between vertices.

@abenne69

This comment has been minimized.

Show comment
Hide comment
@abenne69

abenne69 Feb 11, 2018

Should you also have a line like this in the code below line 13? :
self.distances[(to_node, from_node)] = distance

Should you also have a line like this in the code below line 13? :
self.distances[(to_node, from_node)] = distance

@Iambecomeroot

This comment has been minimized.

Show comment
Hide comment
@Iambecomeroot

Iambecomeroot Mar 26, 2018

@joyrexus your link is broken. Do you have a current link to an algorithm with O(m log n)?

@joyrexus your link is broken. Do you have a current link to an algorithm with O(m log n)?

@samnoonan88

This comment has been minimized.

Show comment
Hide comment
@samnoonan88

samnoonan88 Apr 19, 2018

This looks great, thank you. Can anyone tell me how to pass the values and get it to work? I'd like to demonstrate this to a class and am unsure on how to do this. Any comments or examples would be much appreciated.

This looks great, thank you. Can anyone tell me how to pass the values and get it to work? I'd like to demonstrate this to a class and am unsure on how to do this. Any comments or examples would be much appreciated.

@felipedelosh

This comment has been minimized.

Show comment
Hide comment
@felipedelosh

felipedelosh May 15, 2018

all right but i watch a error in incomplete graph.

g = Graph()
g.add_node('x')
g.add_node('y')
g.add_node('z')
g.add_edge('x', 'y', 100)
g.add_edge('y', 'z', 90)
g.add_edge('z', 'x', 78)

print(dijsktra(g, 'x')) .... error
weight = current_weight + graph.distances[(min_node, edge)]
KeyError: ('x', 'z')

not exist conection to x::z

i change this lines

for edge in graph.edges[min_node]:
  try:
      weight = current_weight + graph.distances[(min_node, edge)]
  except:
      weight = current_weight + math.inf

  if edge not in visited or weight < visited[edge]:
    visited[edge] = weight
    path[edge] = min_node

felipedelosh commented May 15, 2018

all right but i watch a error in incomplete graph.

g = Graph()
g.add_node('x')
g.add_node('y')
g.add_node('z')
g.add_edge('x', 'y', 100)
g.add_edge('y', 'z', 90)
g.add_edge('z', 'x', 78)

print(dijsktra(g, 'x')) .... error
weight = current_weight + graph.distances[(min_node, edge)]
KeyError: ('x', 'z')

not exist conection to x::z

i change this lines

for edge in graph.edges[min_node]:
  try:
      weight = current_weight + graph.distances[(min_node, edge)]
  except:
      weight = current_weight + math.inf

  if edge not in visited or weight < visited[edge]:
    visited[edge] = weight
    path[edge] = min_node
@betandr

This comment has been minimized.

Show comment
Hide comment
@betandr

betandr Jul 16, 2018

I implemented it here as:

def dijkstra(graph, source):
    q = set()
    dist = {}
    prev = {}

    for v in graph.nodes:       # initialization
        dist[v] = INFINITY      # unknown distance from source to v
        prev[v] = INFINITY      # previous node in optimal path from source
        q.add(v)                # all nodes initially in q (unvisited nodes)

    # distance from source to source
    dist[source] = 0

    while q:
        # node with the least distance selected first
        u = min_dist(q, dist)

        q.remove(u)

        if u.label in graph.edges:
            for _, v in graph.edges[u.label].items():
                alt = dist[u] + v.length
                if alt < dist[v.to_node]:
                    # a shorter path to v has been found
                    dist[v.to_node] = alt
                    prev[v.to_node] = u

    return dist, prev

...with the objects:

class Node:
    def __init__(self, label):
        self.label = label
class Edge:
    def __init__(self, to_node, length):
        self.to_node = to_node
        self.length = length
class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = dict()

    def add_node(self, node):
        self.nodes.add(node)

    def add_edge(self, from_node, to_node, length):
        edge = Edge(to_node, length)
        if from_node.label in self.edges:
            from_node_edges = self.edges[from_node.label]
        else:
            self.edges[from_node.label] = dict()
            from_node_edges = self.edges[from_node.label]
        from_node_edges[to_node.label] = edge

betandr commented Jul 16, 2018

I implemented it here as:

def dijkstra(graph, source):
    q = set()
    dist = {}
    prev = {}

    for v in graph.nodes:       # initialization
        dist[v] = INFINITY      # unknown distance from source to v
        prev[v] = INFINITY      # previous node in optimal path from source
        q.add(v)                # all nodes initially in q (unvisited nodes)

    # distance from source to source
    dist[source] = 0

    while q:
        # node with the least distance selected first
        u = min_dist(q, dist)

        q.remove(u)

        if u.label in graph.edges:
            for _, v in graph.edges[u.label].items():
                alt = dist[u] + v.length
                if alt < dist[v.to_node]:
                    # a shorter path to v has been found
                    dist[v.to_node] = alt
                    prev[v.to_node] = u

    return dist, prev

...with the objects:

class Node:
    def __init__(self, label):
        self.label = label
class Edge:
    def __init__(self, to_node, length):
        self.to_node = to_node
        self.length = length
class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = dict()

    def add_node(self, node):
        self.nodes.add(node)

    def add_edge(self, from_node, to_node, length):
        edge = Edge(to_node, length)
        if from_node.label in self.edges:
            from_node_edges = self.edges[from_node.label]
        else:
            self.edges[from_node.label] = dict()
            from_node_edges = self.edges[from_node.label]
        from_node_edges[to_node.label] = edge
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment