最短路径 Dijkstra算法

               
               
                # 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=[[],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
            if not answer[2] and answer[1]>new:
                answer[1]=new
                answer[0]=answer[now][0]+[now]
        #找出最小的那个临时结点，把它标记成肯定结点
        min_value=INFINITE
        mi=now
        for i in answer:
            if not answer[2]:
                if answer[1]min_value: mi,min_value=i,answer[1]
        now=mi
        answer[now][2]=1
        sp += 1
    print
    print "the answer to sp problem"
    print "----------------------------------------------------"
    for i in answer:
        print i," : ",answer
g1=graph('g2')
g1=g1.out()
g1.show()
Dijkstra_sp(g1,'a')
#coding: utf-8
#tulei.py
##一个图中有若干结点,他们的集合称为nodes;
##每个结点(node)有自己的名字,还有邻居,并有到各邻居的权值
import cPickle as p
class node:
    def __init__(self,name):
        self.name=name
        self.father=None
        self.neighbors={}
    def __repr__(self):
        return self.name
    def join(self, cost, node_b):
            self.neighbors[node_b.name]=cost
            node_b.neighbors[self.name]=cost
class graph:
    def __init__(self,name):
        self.name=name
        self.nodes={}
    def who_is(self,name):
        try:
            return self.nodes[name]
        except:
            return None
    def add(self,name_a,cost,name_b):
        # 扩充图内容
        if not self.who_is(name_a):
            a=node(name_a)
            self.nodes[name_a]=a
        if not self.who_is(name_b):
            b=node(name_b)
            self.nodes[name_b]=b
        self.nodes[name_a].join(cost,self.nodes[name_b])
    def save(self):
        # 写入文件
        yes_or_no = raw_input('save or not(s/n): ')
        if yes_or_no == 's':
            f = file(self.name+'.data', 'w')
            p.dump(self, f) # dump the object to a file
            f.close()
    def out(self):
        # 从文件读出
        try:
            f = file(self.name+'.data')
            return p.load(f)
        except:
            print self.name+'.data', "NOT found !"
    def show(self):
        # 显示图内容
        print
        print "this is ", self.name
        print "---------------------------------------------------"
        for i in self.nodes.values():
            print i, i.neighbors
##g1=graph('g1')
##s1='a,15,b'
##while s1 != 'end':
##    s2=s1.split(',')
##    g1.add(s2[0],float(s2[1]),s2[2])
##    s1=raw_input(':')
##g1.show()
##g1.save()