Dijkstra's algorithm help in Python

Question

Im having trouble with Dijkstra's algorithm in python. I understand how the Dijkstra's algorithm works, but im not that good in converting it into code. Is there any way to add the nodes of the path and print them out. I keep getting the path. Thank you.

import heapq
import sys

x = raw_input()
y = raw_input()
class Graph:

def __init__(self):
    self.vertices = {}

def add_vertex(self, name, edges):
    self.vertices[name] = edges

def shortest_path(self, start, finish):
    distances = {} # Distance from start to node
    previous = {}  # Previous node in optimal path from source
    nodes = [] # Priority queue of all nodes in Graph

    for vertex in self.vertices:
        if vertex == start: # Set root node as distance of 0
            distances[vertex] = 0
            heapq.heappush(nodes, [0, vertex])
        else:
            distances[vertex] = sys.maxint
            heapq.heappush(nodes, [sys.maxint, vertex])
        previous[vertex] = None

    while nodes:
        smallest = heapq.heappop(nodes)[1] # Vertex in nodes with smallest distance in distances
        if smallest == finish: # If the closest node is our target we're done so print the path
            path = []
            while previous[smallest]: # Traverse through nodes til we reach the root which is 0
                path.append(smallest)
                smallest = previous[smallest]
            return path
        if distances[smallest] == sys.maxint: # All remaining vertices are inaccessible from source
            break

        for neighbor in self.vertices[smallest]: # Look at all the nodes that this vertex is attached to
            alt = distances[smallest] + self.vertices[smallest][neighbor] # Alternative path distance
            if alt < distances[neighbor]: # If there is a new shortest path update our priority queue (relax)
                distances[neighbor] = alt
                previous[neighbor] = smallest
                for n in nodes:
                    if n[1] == neighbor:
                        n[0] = alt
                        break
                heapq.heapify(nodes)
    return distances

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

g = Graph()
g.add_vertex('A', {'B': 7, 'C': 8})
g.add_vertex('B', {'A': 7, 'F': 2})
g.add_vertex('C', {'A': 8, 'F': 6, 'G': 4})
g.add_vertex('D', {'F': 8})
g.add_vertex('E', {'H': 1})
g.add_vertex('F', {'B': 2, 'C': 6, 'D': 8, 'G': 9, 'H': 3})
g.add_vertex('G', {'C': 4, 'F': 9})
g.add_vertex('H', {'E': 1, 'F': 3})
print g.shortest_path(x, y)

What's the smallest input and output which shows the problem? — Open AI - Opting Out
– Open AI - Opting Out, Commented Nov 10, 2015 at 10:19

Saurabh · Accepted Answer · 2020-07-15 22:47:41Z

3

So I was able to figure out how to use algorithm. Here what I came up with.

import heapq

x = raw_input()
y = raw_input()

def shortestPath(start, end):
    queue,seen = [(0, start, [])], set()
    while True:
        (cost, v, path) = heapq.heappop(queue)
        if v not in seen:
            path = path + [v]
            seen.add(v)
            if v == end:
                return cost, path
            for (next, c) in graph[v].iteritems():
                heapq.heappush(queue, (cost + c, next, path))

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},
}

cost, path = shortestPath(x, y)
print cost, path

edited Jul 15, 2020 at 22:47

Saurabh

7,1565 gold badges48 silver badges58 bronze badges

answered Nov 19, 2015 at 9:41

wallace

771 silver badge10 bronze badges

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

1 Comment

curious_coder Over a year ago

How did you come up with this solution?

Collectives™ on Stack Overflow

Dijkstra's algorithm help in Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related