Python implementation of Dijkstra's Algorithm

gistfile1.py

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

I envy all the people here who can work on this code with no no problem and even if important info is missing! Well, 1) I miss info on where is 'graph' defined (or at least how to create one) and 2) I get "NameError: global name 'defaultdict' is not defined". Any ideas?

@AlkisPis, from collections import defaultdict to clear that error

@JeevaTM, Thanks. You are really very fast ... You replied on Feb 18 to a question I posted on Dec 18! :)) Well, except if you can see the future! :)

This follows the wikipedia definition closely:

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'])
    """

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 it's possible B to A is not the same as A to B. (For example, in a representation of a road network, a 1-way road). I think the user is responsible for adding B to A with the same distance in the usage of add_edge().
You can implement validation/setting that B to A is == A to B, but it would restrict your implementation to solely equidistant and single edge graphs. Would you agree?

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

it is the starting node which has no parent that's why 0