FilesExpand file tree

 master

/

dijkstrashortestpath.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

61 lines (44 loc) · 1.64 KB

 master

/

dijkstrashortestpath.py

Copy path

Top

File metadata and controls

• Code
• Blame

61 lines (44 loc) · 1.64 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

#dijkstra's algorithm

# java code https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/DijkstraShortestPath.java

from priorityqueue import PriorityQueue

from graph import Graph

import sys

def shortest_path(graph, sourceVertex):

min_heap = PriorityQueue(True)

distance = {}

parent = {}

for vertex in graph.all_vertex.values():

min_heap.add_task(sys.maxsize, vertex)

min_heap.change_task_priority(0, sourceVertex)

distance[sourceVertex] = 0

parent[sourceVertex] = None

while min_heap.is_empty() is False:

task = min_heap.peek_task()

weight = min_heap.get_task_priority(task)

current = min_heap.pop_task()

distance[current] = weight

for edge in current.edges:

adjacent = get_other_vertex_for_edge(current, edge)

if min_heap.contains_task(adjacent) is False:

continue

new_distance = distance[current] + edge.weight;

if min_heap.get_task_priority(adjacent) > new_distance:

min_heap.change_task_priority(new_distance, adjacent)

parent[adjacent] = current

return distance

def get_other_vertex_for_edge(vertex, edge):

if edge.vertex1.id == vertex.id:

return edge.vertex2

else:

return edge.vertex1

if __name__ == '__main__':

graph = Graph(False)

graph.add_edge(1,2,5)

graph.add_edge(2,3,2)

graph.add_edge(1,4,9)

graph.add_edge(1,5,3)

graph.add_edge(5,6,2)

graph.add_edge(6,4,2)

graph.add_edge(3,4,3)

distance = shortest_path(graph, graph.all_vertex[1])

print(distance)