Dijkstra's algorithm in python

Question

I am trying to implement Dijkstra's algorithm in python using arrays. This is my implementation.

def extract(Q, w):
        m=0
        minimum=w[0]
        for i in range(len(w)):
                if w[i]<minimum:
                        minimum=w[i]
                        m=i
        return m, Q[m]
def dijkstra(G, s, t='B'):
   Q=[s]
   p={s:None}
   w=[0]
   d={}
        for i in G:
                d[i]=float('inf')
                Q.append(i)
                w.append(d[i])
        d[s]=0
        S=[]
        n=len(Q)
        while Q:
                u=extract(Q,w)[1]
                S.append(u)
                #w.remove(extract(Q, d, w)[0])
                Q.remove(u)
                for v in G[u]:
                        if d[v]>=d[u]+G[u][v]:
                                d[v]=d[u]+G[u][v]
                                p[v]=u
        return d, p
B='B'
A='A'
D='D'
G='G'
E='E'
C='C'
F='F'
G={B:{A:5, D:1, G:2}, A:{B:5, D:3, E:12, F:5}, D:{B:1, G:1, E:1, A:3}, G:{B:2, D:1, C:2}, C:{G:2, E:1, F:16}, E:{A:12, D:1, C:1, F:2}, F:{A:5, E:2, C:16}}
print "Assuming the start vertex to be B:"
print "Shortest distances", dijkstra(G, B)[0]
print "Parents", dijkstra(G, B)[1]

I expect the answer to be:

Assuming the start vertex to be B:
Shortest distances {'A': 4, 'C': 4, 'B': 0, 'E': 2, 'D': 1, 'G': 2, 'F': 4}
Parents {'A': 'D', 'C': 'G', 'B': None, 'E': 'D', 'D': 'B', 'G': 'D', 'F': 'E'}

However, the answer that I get is this:

Assuming the start vertex to be B:
Shortest distances {'A': 4, 'C': 4, 'B': 0, 'E': 2, 'D': 1, 'G': 2, 'F': 10}
Parents {'A': 'D', 'C': 'G', 'B': None, 'E': 'D', 'D': 'B', 'G': 'D', 'F': 'A'}.

For the node F, the program gives the incorrect answer. Can someone please tell me why?

Answer 1

I broke down the wikipedia description into the following pseudo-code on my blog rebrained.com:

Initial state:

1. give nodes two properties - node.visited and node.distance
2. set node.distance = infinity for all nodes except set start node to zero
3. set node.visited = false for all nodes
4. set current node = start node.

Current node loop:

1. if current node = end node, finish and return current.distance & path
2. for all unvisited neighbors, calc their tentative distance (current.distance + edge to neighbor).
3. if tentative distance < neighbor's set distance, overwrite it.
4. set current.isvisited = true.
5. set current = remaining unvisited node with smallest node.distance

http://rebrained.com/?p=392

import sys
def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
    """Find the shortest path btw start & end nodes in a graph"""
    # detect if first time through, set current distance to zero
    if not visited: distances[start]=0
    # if we've found our end node, find the path to it, and return
    if start==end:
        path=[]
        while end != None:
            path.append(end)
            end=predecessors.get(end,None)
        return distances[start], path[::-1]
    # process neighbors as per algorithm, keep track of predecessors
    for neighbor in graph[start]:
        if neighbor not in visited:
            neighbordist = distances.get(neighbor,sys.maxint)
            tentativedist = distances[start] + graph[start][neighbor]
            if tentativedist < neighbordist:
                distances[neighbor] = tentativedist
                predecessors[neighbor]=start
    # neighbors processed, now mark the current node as visited 
    visited.append(start)
    # finds the closest unvisited node to the start 
    unvisiteds = dict((k, distances.get(k,sys.maxint)) for k in graph if k not in visited)
    closestnode = min(unvisiteds, key=unvisiteds.get)
    # now take the closest node and recurse, making it current 
    return shortestpath(graph,closestnode,end,visited,distances,predecessors)
if __name__ == "__main__":
    graph = {'a': {'w': 14, 'x': 7, 'y': 9},
            'b': {'w': 9, 'z': 6},
            'w': {'a': 14, 'b': 9, 'y': 2},
            'x': {'a': 7, 'y': 10, 'z': 15},
            'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11},
            'z': {'b': 6, 'x': 15, 'y': 11}}
    print shortestpath(graph,'a','a')
    print shortestpath(graph,'a','b')
    """
    Expected Result:
        (0, ['a']) 
        (20, ['a', 'y', 'w', 'b'])
        """

Answer 2

Here is my implementation of Dijkstra algorithm using min-priority-queue. Hope it will you.

from collections import defaultdict
from math import floor


class MinPQ:
    """
    each heap element is in form (key value, object handle), while heap
    operations works based on comparing key value and object handle points to
    the corresponding application object.
    """

    def __init__(self, array=[]):
        self._minheap = list(array)
        self._length = len(array)
        self._heapsize = 0
        self._build_min_heap()

    def _left(self, idx):
        return 2*idx+1

    def _right(self, idx):
        return 2*idx+2

    def _parent(self, idx):
        return floor((idx-1)/2)

    def _min_heapify(self, idx):
        left = self._left(idx)
        right = self._right(idx)
        min_idx = idx
        if left <= self._heapsize-1 and self._minheap[left] < self._minheap[min_idx]:
            min_idx = left
        if right <= self._heapsize-1 and self._minheap[right] < self._minheap[min_idx]:
            min_idx = right
        if min_idx != idx:
            self._minheap[idx], self._minheap[min_idx] = self._minheap[min_idx], self._minheap[idx]
            self._min_heapify(min_idx)

    def _build_min_heap(self):
        self._heapsize = self._length
        mid_id = int(self._heapsize-1)-1
        for i in range(mid_id, -1, -1):
            self._min_heapify(i)

    def decrease_key(self, idx, new_key):
        while idx > 0 and new_key < self._minheap[self._parent(idx)]:
            self._minheap[idx] = self._minheap[self._parent(idx)]
            idx = self._parent(idx)
        self._minheap[idx] = new_key

    def extract_min(self):
        minimum = self._minheap[0]
        self._minheap[0] = self._minheap[self._heapsize-1]
        self._heapsize = self._heapsize - 1
        self._min_heapify(0)
        return minimum

    def insert(self, item):
        self._minheap.append(item)
        self._heapsize = self._heapsize + 1
        self.decrease_key(self._heapsize-1, item)

    @property
    def minimum(self):
        return self._minheap[0]

    def is_empty(self):
        return self._heapsize == 0

    def __str__(self):
        return str(self._minheap)

    __repr__ = __str__

    def __len__(self):
        return self._heapsize


class DiGraph:
    def __init__(self, edges=None):
        self.adj_list = defaultdict(list)
        self.add_weighted_edges(edges)

    @property
    def nodes(self):
        nodes = set()
        nodes.update(self.adj_list.keys())
        for node in self.adj_list.keys():
            for neighbor, weight in self.adj_list[node]:
                nodes.add(neighbor)
        return list(nodes)

    def add_weighted_edges(self, edges):
        if edges is None:
            return None
        for edge in edges:
            self.add_weighted_edge(edge)

    def add_weighted_edge(self, edge):
        node1, node2, weight = edge
        self.adj_list[node1].append((node2, weight))

    def weight(self, tail, head):
        for node, weight in self.adj_list[tail]:
            if node == head:
                return weight
        return None


def relax(min_heapq, dist, graph, u, v):
    if dist[v] > dist[u] + graph.weight(u, v):
        dist[v] = dist[u] + graph.weight(u, v)
        min_heapq.insert((dist[v], v))


def dijkstra(graph, start):
    # initialize
    dist = dict.fromkeys(graph.nodes, float('inf'))
    dist[start] = 0
    min_heapq = MinPQ()
    min_heapq.insert((0, start))

    while not min_heapq.is_empty():
        distance, u = min_heapq.extract_min()
        # we may add a node multiple time in priority queue, but we process it
        # only once
        if distance > dist[u]:
            continue
        for neighbor, weight in graph.adj_list[u]:
            relax(min_heapq, dist, graph, u, neighbor)

    return dist

if __name__ == "__main__":
    edges = [('s', 't', 10), ('t', 'x', 1), ('s', 'y', 5), ('y', 't', 3), ('t', 'y', 2), 
             ('y', 'x', 9), ('y', 'z', 2), ('z', 's', 7), ('x', 'z', 4), ('z', 'x', 6)]
    digraph = DiGraph(edges)
    res = dijkstra(digraph, 's')
    print(res)

Answer 3

This is not my answer - my prof did it much more efficiently than my attempt. Here is his approach, obviously using helper-functions for the repetitive tasks

def dijkstra(graph, source):

    vertices, edges = graph
    dist = dict()
    previous = dict()

    for vertex in vertices:
        dist[vertex] = float("inf")
        previous[vertex] = None

    dist[source] = 0
    Q = set(vertices)

    while len(Q) > 0:
        u = minimum_distance(dist, Q)
        print('Currently considering', u, 'with a distance of', dist[u])
        Q.remove(u)

        if dist[u] == float('inf'):
            break

        n = get_neighbours(graph, u)
        for vertex in n:
            alt = dist[u] + dist_between(graph, u, vertex)
            if alt < dist[vertex]:
                dist[vertex] = alt
                previous[vertex] = u

    return previous

Given a graph

({'A', 'B', 'C', 'D'}, {('A', 'B', 5), ('B', 'A', 5), ('B', 'C', 10), ('B', 'D', 6), ('C', 'D', 2), ('D', 'C', 2)})

the command print(dijkstra(graph, 'A') yields

Currently considering A with a distance of 0

Currently considering B with a distance of 5

Currently considering D with a distance of 11

Currently considering C with a distance of 13

id est:

{'C': 'D', 'D': 'B', 'A': None, 'B': 'A'} => in random order

Answer 4

I implement Dijkstra using priority-queue. Apart from that, I also implement min-heap myself. Hope this will help you.

from collections import defaultdict


class MinPQ:
    """
    each heap element is in form (key value, object handle), while heap
    operations works based on comparing key value and object handle points to
    the corresponding application object.
    """

    def __init__(self, array=[]):
        self._minheap = list(array)
        self._length = len(array)
        self._heapsize = 0
        self._build_min_heap()

    def _left(self, idx):
        return 2*idx+1

    def _right(self, idx):
        return 2*idx+2

    def _parent(self, idx):
        return int((idx-1)/2)

    def _min_heapify(self, idx):
        left = self._left(idx)
        right = self._right(idx)
        min_idx = idx
        if left <= self._heapsize-1 and self._minheap[left] < self._minheap[min_idx]:
            min_idx = left
        if right <= self._heapsize-1 and self._minheap[right] < self._minheap[min_idx]:
            min_idx = right
        if min_idx != idx:
            self._minheap[idx], self._minheap[min_idx] = self._minheap[min_idx], self._minheap[idx]
            self._min_heapify(min_idx)

    def _build_min_heap(self):
        self._heapsize = self._length
        mid_id = int((self._heapsize)/2)-1
        for i in range(mid_id, -1, -1):
            self._min_heapify(i)

    def decrease_key(self, idx, new_key):
        while idx > 0 and new_key < self._minheap[self._parent(idx)]:
            self._minheap[idx] = self._minheap[self._parent(idx)]
            idx = self._parent(idx)
        self._minheap[idx] = new_key

    def extract_min(self):
        if self._heapsize < 1:
            raise IndexError
        minimum = self._minheap[0]
        self._minheap[0] = self._minheap[self._heapsize-1]
        self._heapsize = self._heapsize - 1
        self._min_heapify(0)
        return minimum

    def insert(self, item):
        self._minheap.append(item)
        self._heapsize = self._heapsize + 1
        self.decrease_key(self._heapsize-1, item)

    @property
    def minimum(self):
        return self._minheap[0]

    def is_empty(self):
        return self._heapsize == 0

    def __str__(self):
        return str(self._minheap)

    __repr__ = __str__

    def __len__(self):
        return self._heapsize


class DiGraph:
    def __init__(self, edges=None):
        self.adj_list = defaultdict(list)
        self.add_weighted_edges(edges)

    @property
    def nodes(self):
        nodes = set()
        nodes.update(self.adj_list.keys())
        for node in self.adj_list.keys():
            for neighbor, weight in self.adj_list[node]:
                nodes.add(neighbor)
        return list(nodes)

    def add_weighted_edges(self, edges):
        if edges is None:
            return None
        for edge in edges:
            self.add_weighted_edge(edge)

    def add_weighted_edge(self, edge):
        node1, node2, weight = edge
        self.adj_list[node1].append((node2, weight))

    def weight(self, tail, head):
        for node, weight in self.adj_list[tail]:
            if node == head:
                return weight
        return None


def relax(min_heapq, dist, graph, u, v):
    if dist[v] > dist[u] + graph.weight(u, v):
        dist[v] = dist[u] + graph.weight(u, v)
        min_heapq.insert((dist[v], v))


def dijkstra(graph, start):
    # initialize
    dist = dict.fromkeys(graph.nodes, float('inf'))
    dist[start] = 0
    min_heapq = MinPQ()
    min_heapq.insert((0, start))

    while not min_heapq.is_empty():
        distance, u = min_heapq.extract_min()
        # we may add a node multiple time in priority queue, but we process it
        # only once
        if distance > dist[u]:
            continue
        for neighbor, weight in graph.adj_list[u]:
            relax(min_heapq, dist, graph, u, neighbor)

    return dist

Answer 5

Set a breakpoint in extract. You will see that you delete entries from Q but never from w. Everything else is a dict, but Q/w are a paired array which you do not keep up to date. You have to keep those two in sync, or replace them with a dict. Special note: Eventually, after the algorithm is working, you may want to replace Q/w with a list of edges and re-code the "extract" function with a priority queue (heapq module).

Additionally, you will see that w always has weights of 0 for the source, and 'inf' for all other nodes. You completely skipped the critical step where you update the candidate distances.

So you are basically always taking the first path you encounter, rather than selecting the shortest path. You later compute the actual distance of that path, so the returned array of distances has actual values, but they were chosen arbitrarily, and you have no reason to expect them to be shortest.

After you (incorrectly) find the next node, you look at all of its edges. This should have been the critical step I mentioned above in the second paragraph, where you update the candidates for the next node. Instead you do something completely different: You appear to be looping through all the previous solutions (which are guaranteed correct and should be left alone, if you correctly implement dijkstra), and you look for a two-step solution from source->current->any. The correct intent for looking at those would have been to add the next candidate from previous paths to the next node, but because they never get added, you don't look at (previous shortest path) + (one step), you only look at literally two node solutions.

So basically, you are looping through all possible two-node paths from source in order to find the shortest paths. This is a complete error and has nothing to do with dijkstra. But it almost works on your tiny tiny graph where most of the correct shortest paths are two-step paths.

(ps: I agree with everyone about your variable names. You would have done much better if you use verbose names telling what those variables represent. I had to rename them before I got anywhere analyzing your code.)

Answer 6

I wrote it in a more verbose form to make it clearer for a novice reader:

def get_parent(pos):
    return (pos + 1) // 2 - 1


def get_children(pos):
    right = (pos + 1) * 2
    left = right - 1
    return left, right


def swap(array, a, b):
    array[a], array[b] = array[b], array[a]


class Heap:

    def __init__(self):
        self._array = []

    def peek(self):
        return self._array[0] if self._array else None

    def _get_smallest_child(self, parent):
        return min([
            it
            for it in get_children(parent)
            if it < len(self._array)
        ], key=lambda it: self._array[it], default=-1)

    def _sift_down(self):
        parent = 0
        smallest = self._get_smallest_child(parent)
        while smallest != -1 and self._array[smallest] < self._array[parent]:
            swap(self._array, smallest, parent)
            parent, smallest = smallest, self._get_smallest_child(smallest)

    def pop(self):
        if not self._array:
            return None
        swap(self._array, 0, len(self._array) - 1)
        node = self._array.pop()
        self._sift_down()
        return node

    def _sift_up(self):
        index = len(self._array) - 1
        parent = get_parent(index)
        while parent != -1 and self._array[index] < self._array[parent]:
            swap(self._array, index, parent)
            index, parent = parent, get_parent(parent)

    def add(self, item):
        self._array.append(item)
        self._sift_up()

    def __bool__(self):
        return bool(self._array)


def backtrack(best_parents, start, end):
    if end not in best_parents:
        return None
    cursor = end
    path = [cursor]
    while cursor in best_parents:
        cursor = best_parents[cursor]
        path.append(cursor)
        if cursor == start:
            return list(reversed(path))
    return None


def dijkstra(weighted_graph, start, end):
    """
    Calculate the shortest path for a directed weighted graph.

    Node can be virtually any hashable datatype.

    :param start: starting node
    :param end: ending node
    :param weighted_graph: {"node1": {"node2": weight, ...}, ...}
    :return: ["START", ... nodes between ..., "END"] or None, if there is no
            path
    """
    distances = {i: float("inf") for i in weighted_graph}
    best_parents = {i: None for i in weighted_graph}

    to_visit = Heap()
    to_visit.add((0, start))
    distances[start] = 0

    visited = set()

    while to_visit:
        src_distance, source = to_visit.pop()
        if src_distance > distances[source]:
            continue
        if source == end:
            break
        visited.add(source)
        for target, distance in weighted_graph[source].items():
            if target in visited:
                continue
            new_dist = distances[source] + weighted_graph[source][target]
            if distances[target] > new_dist:
                distances[target] = new_dist
                best_parents[target] = source
                to_visit.add((new_dist, target))

    return backtrack(best_parents, start, end)