Nodes shortest path - Dijkstra

dijkstra.py

import random
from igraph import *
from priodict import priorityDictionary


def dijkstra(graph, source, target=None):
    distances = {}
    predec = {}
    queue = priorityDictionary()
    queue[source] = 0

    for node_source in queue:
        distances[node_source] = queue[node_source]
        if node_source == target:
            break
        for node_target in graph.successors(node_source):
            edge_n = graph.get_eid(node_source, node_target)
            length = distances[node_source] + graph.es[edge_n]['weight']
            if node_target not in distances and (
                node_target not in queue or length < queue[node_target]):
                queue[node_target] = length
                predec[node_target] = node_source

    return distances, predec

def shortest_path(graph, source, target):
    distances, predec = dijkstra(graph, source, target)
    path = []
    while True:
        path.insert(0, target)
        if target == source:
            break
        try:
            target = predec[target]
        except KeyError:
            path = []  # Not path found
            break
    return path

def generate_graph(num_nodes=100):
    g = Graph.Erdos_Renyi(n=num_nodes, p=0.1, directed=True)
    weights = [random.randrange(0, g.ecount()) for _ in xrange(0, g.ecount())]
    g.es["weight"] = weights
    return g


if __name__ == '__main__':
    g = generate_graph(60)
    print shortest_path(g, 1, 9)