Dijkstra’s Algorithm in python

Question

I am trying to implement Dijkstra’s algorithm on my python code but I can't really get the algorithm right. The algorithm I am using is from this youtube link: https://www.youtube.com/watch?v=pVfj6mxhdMw

So basically my class has these 3 variables:

self.nodes = [] #a,b,c
self.neighbours = {} # a:[b,c], b:[c], c:[a]
self.weights = {} #[a,b] = 2, [a,c] = 5

Here is how I partially implemented my shortest path function using the algorithm provided in the video:

def dijkstra(self, start, end):

    nodes = {}

    for n in self.nodes:
        if n == start:
                nodes[n] = 0
        else:
                nodes[n] = float('inf')

    unvisited = self.neighbours
    visited = []
    current_node = start
    current_distance = 0

    while unvisited:
        for n in unvisited[current_node]:
            print(n)
            #calc_weight = nodes[n] + self.weights[n, current_node]
            #if (unvisited[n] is None or calc_weight > nodes[n]):
                    #nodes[n] = calc_weight
        visited.append(current_node)
        del unvisited[current_node]

        if not unvisited: break

I havent really completed because I know I missing something out somewhere. Can someone please help me with this. Thank you

@Shasha99 Nope. I can't seem to get that algorithm right. The previous comments didnt help, one led me to another algorithm which isnt really an answer, while the second led me to a hello world program. — Kumayl Fazal
– Kumayl Fazal, Commented Dec 1, 2016 at 20:51
I was actually talking about this: code.hackerearth.com/0ed99eZ You should implement min heap for the optimal solution. — Shasha99
– Shasha99, Commented Dec 2, 2016 at 6:00

Kumayl Fazal · Accepted Answer · 2016-12-01 22:47:31Z

0

def dijkstra(self, start, end):

    nodes = self.neighbours #{'A': {'B':2}, 'B': {'C':4}, ... }

    unvisited = {n: 1000 for n in self.nodes} #unvisited node & distance
    unvisited[start] = 0 #set start vertex to 0
    visited = {} #list of all visited nodes
    parent = {} #predecessors

    while unvisited:
        min_node = min(unvisited, key=unvisited.get) #get smallest distance

        for neighbour in nodes[min_node].items():
            if neighbour not in visited:
                new_distance = unvisited[min_node] + nodes[min_node][neighbour]
                if new_distance < unvisited[neighbour]:
                    unvisited[neighbour] = new_distance
                    parent[neighbour] = min_node

        visited[min_node] = unvisited[min_node]
        unvisited.pop(min_node)

    print(parent, visited)

answered Dec 1, 2016 at 22:47

Kumayl Fazal

111 silver badge4 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Ionut Ticus Over a year ago

In order to exit the loop when the target (end) node is hit you need: if min_node == end: break

Ionut Ticus Over a year ago

For undefined edges you need nodes[min_node].get(neighbour, 1000) instead of nodes[min_node][neighbour]

Ionut Ticus Over a year ago

Also, using float("inf") is preferable instead of 1000.

Collectives™ on Stack Overflow

Dijkstra’s Algorithm in python

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related