Dijkstra algoritm implementation

dijkstra.py

# vim: set fileencoding=utf-8
import random
from Queue import Queue
random.seed(1234)

# initialization ------------------------------------------
N = 10
pStart = 0
pEnd = N - 1

F = [[0.0]*N for i in xrange(N)]
for i in xrange(N):
    for j in range(i, N):
        if i != j:
            F[i][j] = F[j][i] = random.random()
B = [False for j in xrange(N)]
S = [10.0 ** 10] * N
S[pStart] = 0.0

Pmin = [0]*N

# ALGORITM start ------------------------------------------
nextPoints = Queue()
nextPoints.put(pStart)

while not nextPoints.empty():
    p = nextPoints.get()
    B[p] = True
    for j in xrange(N):
        if B[j] == False: 
            nextPoints.put(j)
        if S[p] + F[p][j] < S[j]:
            Pmin[j] = p
            S[j] = S[p] + F[p][j]

# ALGORITM end --------------------------------------------
assert B[pEnd] == True

print "Transition cost matrix (F)"
for l in F:
    for v in l:
        print "%.3f" % (v,),
    print

print "State minimums (S)"
for v in S:
    print "%.3f" % (v,),
print

print "Point minima transitions (Pmin)"
print Pmin

print "Best way from", pEnd, "to", pStart
p = pEnd
while p != pStart:
    print p,
    p = Pmin[p]
print p

"""
Transition cost matrix (F)
0.000 0.966 0.441 0.007 0.911 0.939 0.582 0.672 0.084 0.766
0.966 0.000 0.237 0.031 0.789 0.346 0.623 0.616 0.149 0.183
0.441 0.237 0.000 0.114 0.015 0.487 0.965 0.065 0.541 0.466
0.007 0.031 0.114 0.000 0.601 0.089 0.579 0.270 0.556 0.645
0.911 0.789 0.015 0.601 0.000 0.481 0.355 0.249 0.934 0.453
0.939 0.346 0.487 0.089 0.481 0.000 0.530 0.019 0.508 0.006
0.582 0.623 0.965 0.579 0.355 0.530 0.000 0.144 0.473 0.377
0.672 0.616 0.065 0.270 0.249 0.019 0.144 0.000 0.054 0.588
0.084 0.149 0.541 0.556 0.934 0.508 0.473 0.054 0.000 0.164
0.766 0.183 0.466 0.645 0.453 0.006 0.377 0.588 0.164 0.000

State minimums (S)
0.000 0.038 0.122 0.007 0.137 0.096 0.259 0.116 0.084 0.102

Point minima transitions (Pmin)
[0, 3, 3, 0, 2, 3, 7, 5, 0, 5]

Best way from 9 to 0
9 5 3 0

"""