Home > GAE和编程 > 最短路径只Dijkstra算法python实现

最短路径只Dijkstra算法python实现

September 12th, 2009 发表评论 阅读评论

最短路径 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[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')



#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()

转载请以超链接注明来自  云在天边看世界
本文永久链接  http://www.tangblog.info/2009/09/12/Dijkstra_python.html

分类: GAE和编程 标签:

  1. 本文目前尚无任何评论,抢个沙发?
  1. 本文目前尚无任何 trackbacks 和 pingbacks.
/static/smilies/icon_twisted.gif /static/smilies/icon_smile.gif /static/smilies/icon_cry.gif /static/smilies/icon_question.gif /static/smilies/icon_razz.gif /static/smilies/icon_mrgreen.gif /static/smilies/icon_sad.gif /static/smilies/icon_evil.gif /static/smilies/icon_exclaim.gif /static/smilies/icon_redface.gif /static/smilies/icon_biggrin.gif /static/smilies/icon_surprised.gif /static/smilies/icon_eek.gif /static/smilies/icon_confused.gif /static/smilies/icon_cool.gif /static/smilies/icon_lol.gif /static/smilies/icon_mad.gif /static/smilies/icon_rolleyes.gif /static/smilies/icon_wink.gif /static/smilies/icon_idea.gif /static/smilies/icon_arrow.gif /static/smilies/icon_neutral.gif
capacha 请输入验证码(不区分大小写)