云在天边看世界

# coding: utf-8

#shortest_path.py


## 最短路径
## 使用Dijkstra算法找给定结点到图上其它各点的最短路径
##

##参数g是被遍历的图, A是给定结点的名字

##Dijkstra算法的思想是：
##起初，只有一个结点A，此结点到自己的最短路径确定，值为0
##下一步，扩展此结点的所有相邻结点，形成集合{}。
##
##因为相邻结点都在{}了，所以最近相邻的那个结点B的最短路径也确定，就是AB
##否则，A到B的最短路径必经过C，C属于{},且AC大于AB；故AB一定是到B的肯定最短路径
##
##其它结点的最短路径尚不能确定，因为信息还没完全掌握
##但它们有临时最短路径AC
##
##扩展B的所有相邻结点（未被扩展过的和已经扩展过的）
##刷新临时最短路径（当然已找到肯定最短路径的那些结点不必刷新）
##在所有临时最短路径中找到最短的那个，为肯定最短路径，原因前面论证过
##再扩展，在刷新，再取最小，重复这个循环（实际上我现在已经讲到第二次循环了）
##
##在以后的每步过程中，我们会保证，找到肯定最短路径的所有点都紧紧粘成一团
##且外面裹着一层临时最短路径结点
##注意：
##第一，只有一层，这使得不确定性只有一层，而不会层层传播
##（所谓一层指的是，它必与某个肯定结点直接相连）
##第二，裸露的肯定最短路径点马上要被包起来，不得延迟
##
##我们还保证了，通过所有已知的肯定结点，那些临时点的值都是最优的
##
##因此，我们保证了，这些临时点中最小的那一个一定是肯定结点：
##从里面走最优的；没有更优的办法冲出包围

##当所有结点都加进去时，信息已经完全
##我们做最后一次刷新，这时，所有临时结点也变成肯定结点
##
##错错错，必须使得所有结点都标记为肯定结点
##否则，循环不应退出


INFINITE=1000
from tulei import *

#参数g表示所给图，A表示给定图上的一结点
def Dijkstra_sp(g,A):
     #初始化解
     answer={}
    for i in g.nodes.keys():
         #第一位表示路径，第二位表示距离值，第三位表示肯定值
         answer[i]=[[],INFINITE,0]
     #初始化局部信息图结点列表
     part_nodes=[A]

     now = A
     answer[A]=[[],0,1]

     #循环，控制条件是信息图的不完整性
     sp=1
## while len(part_nodes) < len(g.nodes):
    while sp < len(g.nodes):

        for i in g.who_is(now).neighbors:
## if i not in part_nodes:
## part_nodes.append(i)
             new=answer[now][1]+ g.who_is(now).neighbors[i]
            if not answer[i][2] and answer[i][1]>new:
                 answer[i][1]=new
                 answer[i][0]=answer[now][0]+[now]
         #找出最小的那个临时结点，把它标记成肯定结点
         min_value=INFINITE
         mi=now
        for i in answer:
            if not answer[i][2]:
                if answer[i][1]<min_value: mi,min_value=i,answer[i][1]
         now=mi
         answer[now][2]=1
         sp += 1
    print
    print "the answer to sp problem"
    print "----------------------------------------------------"
    for i in answer:
        print i," : ",answer[i]

g1=graph('g2')
g1=g1.out()
g1.show()
Dijkstra_sp(g1,'a')