Programing problems

From stacky wiki
Revision as of 08:57, 23 February 2012 by Anton (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Given an undirected graph G having N (1<N<=1000) vertices and positive weights. Find the shortest path from vertex 1 to vertex N, or state that such path doesn't exist.

# G a set or list of triples (i,j,w) with i<j, and w>0

N=4
G=[(1,2,1),(1,3,1),(2,3,1),(3,4,1),(2,4,1)]

shortestpath = [None]*(N+1) # None=infty
shortestpath[1]=0
for x in xrange(N):
    for (i,j,w) in G:
        if shortestpath[i] is not None and shortestpath[j] is None:
            shortestpath[j]=shortestpath[i]+w
            continue
        if shortestpath[j] is not None and shortestpath[i] is None:
            shortestpath[i]=shortestpath[j]+w
            continue
        shortestpath[i]=min(shortestpath[i],shortestpath[j]+w)
        shortestpath[j]=min(shortestpath[j],shortestpath[i]+w)

print shortestpath[N]