Dijkstra for the CSH in-class graph

dijkstra.py

#
# Version 1 
#
# - data stored as node and edge sets
# - frontier is set of (src, dst, weight)
# - far too many O(n) loops
#

# Load graph 
nodes = set()
edges = set()
for line in file('graph.txt'):
    src, dst, weight = line.strip().split(',')
    nodes.add(src)
    nodes.add(dst)
    edges.add((src,dst,int(weight)))

print nodes
print edges

# Find shortest path
def shortest_path(src, dst):
    
    frontier = set()
    explored = set()
    distances = dict()

    # Initial Frontier
    for edge in edges:
        if edge[0] == src:
            frontier.add(edge)

    distances[src] = 0
    explored.add(src)

    # Main loop
    while len(frontier) > 0:

        #print locals()

        # Find best candidate
        lowest = (None, None, float('inf'))
        for edge in frontier:
            if edge[1] not in explored:
                if distances[edge[0]] + edge[2] <= lowest[2]:
                    lowest = edge
        
        # Update the path cost
        distances[lowest[1]] = min(
            distances.get(lowest[1], float('inf')),
            distances[lowest[0]] + lowest[2],
        )
        #print 'remove', lowest
        frontier.remove(lowest)
        explored.add(lowest[0])

        if lowest[1] != dst:

            # Expand frontier
            for edge in edges:
                if edge[0] == lowest[1]:
                    frontier.add(edge)
                    #print 'add', edge

    #print locals()

    cur = src
    path = list()
    while cur != dst:
        # outgoing from our node
        out = [edge for edge in edges if edge[0] == cur]

        #print cur, out

        # lowest total cost
        if out:
            lowest = out[0]
            for edge in edges:
                if edge[0] == cur:
                    if distances[edge[1]] < distances[lowest[1]]:
                        lowest = edge
                        #print 'lowest', lowest
            path.append(lowest)
            cur = lowest[1]
        else:
            raise ValueError('path not found')

    return path
        

print shortest_path('0','4')
print shortest_path('0','2')

#
# Version 2
#
# - data stored adjacency dict (networkx inspired)
# - frontier is set of (src, dst, weight)
# - faster, frontier tuple, updates are awkward
#

# Load graph, adjacency list style
G = {}
for s,d,w in (l.strip().split(',') for l in file('graph.txt')):
    G.setdefault(s, {})[d] = {'weight':int(w)}
print G

# Find shortest path
def shortest_path2(src, dst):

    # Frontier
    frontier = set()
    frontier.update(
        (src, n, G[src][n]['weight']) 
        for n in G.setdefault(src, {}).keys()
    )

    dist = dict()
    dist[src] = 0
    explored = set([src])

    # Main loop
    while len(frontier) > 0:

        # Find best candidate
        lowest = iter(frontier).next()
        lsource, ldest, lweight = lowest
        for edge in frontier:
            source, dest, weight = edge
            if dest not in explored:
                # Overall shortest path
                if weight + dist[source] <= lweight:
                    lowest = (source, dest, weight)
                    lsource, ldest, lweight = lowest
        
        # Update the path cost
        dist[ldest] = dist[lsource] + lweight
        frontier.remove(lowest)
        explored.add(lsource)

        # Expand frontier
        frontier.update(
            (ldest, n, G[ldest][n]['weight']) 
            for n in G.setdefault(ldest, {}).keys()
        )

    # Reconstruct shortest path
    cur = src
    path = list()
    while cur != dst:
        if G[cur]:
            lowest = G[cur].keys()[0]
            for d in G[cur]:
                if dist[d] < dist[lowest]:
                    lowest = d
            path.append(lowest)
            cur = lowest
        else:
            raise ValueError('path not found')
    return path

print shortest_path2('0','4')
print shortest_path2('0','2')

#
# Version 3
#
# - data stored adjacency dict (networkx inspired)
# - frontier is just nodes + a "cur" node
# - most straightforward so far
#

# Find shortest path
def shortest_path3(src, dst):

    frontier = set((src, d) for d in G.setdefault(src, {}).keys())
    explored = set([src])

    dist = {src:0}
    cur = src

    # Main loop
    while len(frontier) > 0:

        # Find best candidate
        cs, cd = candidate = iter(frontier).next()
        for s, d in frontier:
            if d not in explored:
                # Overall shortest path
                if dist[s] + G[s][d]['weight'] < \
                   dist[cs] + G[cs][cd]['weight']:
                    cs, cd = candidate = s,d
        
        # Update the path cost
        dist[cd] = dist[cur] + G[cs][cd]['weight']
        frontier.remove(candidate)
        explored.add(cur)
        cur = cd

        # Expand frontier
        frontier.update((cur,d) for d in G.setdefault(cur, {}).keys())

    # Reconstruct shortest path
    cur = src
    path = list()
    while cur != dst:
        if G[cur]:
            lowest = G[cur].keys()[0]
            for d in G[cur]:
                if dist[d] < dist[lowest]:
                    lowest = d
            path.append(lowest)
            cur = lowest
        else:
            raise ValueError('path not found')
    return path

print shortest_path3('0','4')
print shortest_path3('0','2')

graph.txt

0,1,10
0,4,100
0,3,30
1,2,50
2,4,10
3,2,20
3,4,60