热线电话：13121318867

登录
首页精彩阅读python编写的最短路径算法
python编写的最短路径算法
2017-08-20
收藏

python编写的最短路径算法

一心想学习算法，很少去真正静下心来去研究，前几天趁着周末去了解了最短路径的资料，用python写了一个最短路径算法。算法是基于带权无向图去寻找两个点之间的最短路径，数据存储用邻接矩阵记录。首先画出一幅无向图如下，标出各个节点之间的权值。

其中对应索引：

A ——> 0

B——> 1

C——> 2

D——>3

E——> 4

F——> 5

G——> 6

邻接矩阵表示无向图：

算法思想是通过Dijkstra算法结合自身想法实现的。大致思路是：从起始点开始，搜索周围的路径，记录每个点到起始点的权值存到已标记权值节点字典A，将起始点存入已遍历列表B，然后再遍历已标记权值节点字典A，搜索节点周围的路径，如果周围节点存在于表B，比较累加权值，新权值小于已有权值则更新权值和来源节点，否则什么都不做；如果不存在与表B，则添加节点和权值和来源节点到表A，直到搜索到终点则结束。

这时最短路径存在于表A中，得到终点的权值和来源路径，向上递推到起始点，即可得到最短路径，下面是代码：


# -*-coding:utf-8 -*-
classDijkstraExtendPath():
  def__init__(self, node_map):
    self.node_map=node_map
    self.node_length=len(node_map)
    self.used_node_list=[]
    self.collected_node_dict={}
  def__call__(self, from_node, to_node):
    self.from_node=from_node
    self.to_node=to_node
    self._init_dijkstra()
    returnself._format_path()
  def_init_dijkstra(self):
    self.used_node_list.append(self.from_node)
    self.collected_node_dict[self.from_node]=[0,-1]
    forindex1, node1inenumerate(self.node_map[self.from_node]):
      ifnode1:
        self.collected_node_dict[index1]=[node1,self.from_node]
    self._foreach_dijkstra()
  def_foreach_dijkstra(self):
    iflen(self.used_node_list)==self.node_length-1:
      return
    forkey, valinself.collected_node_dict.items():# 遍历已有权值节点
      ifkeynotinself.used_node_listandkey !=to_node:
        self.used_node_list.append(key)
      else:
        continue
      forindex1, node1inenumerate(self.node_map[key]):# 对节点进行遍历
        # 如果节点在权值节点中并且权值大于新权值
        ifnode1andindex1inself.collected_node_dictandself.collected_node_dict[index1][0] > node1+val[0]:
          self.collected_node_dict[index1][0]=node1+val[0]# 更新权值
          self.collected_node_dict[index1][1]=key
        elifnode1andindex1notinself.collected_node_dict:
          self.collected_node_dict[index1]=[node1+val[0], key]
    self._foreach_dijkstra()
  def_format_path(self):
    node_list=[]
    temp_node=self.to_node
    node_list.append((temp_node,self.collected_node_dict[temp_node][0]))
    whileself.collected_node_dict[temp_node][1] !=-1:
      temp_node=self.collected_node_dict[temp_node][1]
      node_list.append((temp_node,self.collected_node_dict[temp_node][0]))
    node_list.reverse()
    returnnode_list
defset_node_map(node_map, node, node_list):
  forx, y, valinnode_list:
    node_map[node.index(x)][node.index(y)]=node_map[node.index(y)][node.index(x)]=val
if__name__=="__main__":
  node=['A','B','C','D','E','F','G']
  node_list=[('A','F',9), ('A','B',10), ('A','G',15), ('B','F',2),
         ('G','F',3), ('G','E',12), ('G','C',10), ('C','E',1),
         ('E','D',7)]
  node_map=[[0forvalinxrange(len(node))]forvalinxrange(len(node))]
  set_node_map(node_map, node, node_list)
  # A -->; D
  from_node=node.index('A')
  to_node=node.index('D')
  dijkstrapath=DijkstraPath(node_map)
  path=dijkstrapath(from_node, to_node)
  printpath

运行结果：

再来一例：

# -*- coding: utf-8 -*-
importitertools
importre
importmath
 
defcombination(lst): #全排序
  lists=[]
  liter=itertools.permutations(lst)
  forltsinlist(liter):
    lt=''.join(lts)
    lists.append(lt)
  returnlists
 
defcoord(lst):  #坐标输入
  coordinates=dict()
  printu'请输入坐标：（格式为A:7 17）'
  p=re.compile(r"\d+")
  forcharinlst:
    str=raw_input(char+':')
    dot=p.findall(str)
    coordinates[char]=[dot[0],dot[1]]
  printcoordinates
  returncoordinates
 
defrepeat(lst): #删除重复组合
  forilistinlst:
    forkinxrange(len(ilist)):
      st=(ilist[k:],ilist[:k])
      strs=''.join(st)
      forjlistinlst:
        if(cmp(strs,jlist)==0):
          lst.remove(jlist)
    forkinxrange(len(ilist)):
      st=(ilist[k:],ilist[:k])
      strs=''.join(st)
      forjlistinlst:
        if(cmp(strs[::-1],jlist)==0):
          lst.remove(jlist)
    lst.append(ilist)
    printlst
  returnlst
 
defcount(lst,coordinates):#计算各路径
  way=dict()
  forstrinlst:
    str=str+str[:1]
    length=0
    foriinrange(len(str)-1):
      x=abs(float(coordinates[str[i]][0])-float(coordinates[str[i+1]][0]) )
      y=abs(float(coordinates[str[i] ][1])-float(coordinates[str[i+1] ][1]) )
      length+=math.sqrt(x**2+y**2)
    way[str[:len(str)-1]]=length
  returnway
 
if__name__=="__main__":
  printu'请输入图节点：'
  rlist=list(raw_input())
  coordinates=coord(rlist)
 
  list_directive=combination(rlist)
#  print "有方向完全图所有路径为:",list_directive
#  for it in list_directive:
#    print it
  printu'有方向完全图所有路径总数:',len(list_directive),"\n"
 
#无方向完全图
  list_directive=repeat(list_directive)
  list_directive=repeat(list_directive)
#  print "无方向完全图所有路径为:",list_directive
  printu'无方向完全图所有路径为:'
  foritinlist_directive:
    printit
  printu'无方向完全图所有路径总数:',len(list_directive)
 
  ways=count(list_directive,coordinates)
  printu'路径排序如下：'
  fordstrinsorted(ways.iteritems(), key=lambdad:d[1], reverse=False):
    printdstr
  raw_input()

以上就是本文给大家分享的全部内容了，希望大家能够喜欢，能够学习python有所帮助。



CDA数据分析师考试相关入口一览（建议收藏）：

▷ 想报名CDA认证考试，点击>>>   “CDA报名” 了解CDA考试详情；

▷ 想加入CDA考试题库，点击>>> “CDA题库” 了解CDA考试详情；

▷ 想学习CDA考试教材，点击>>> “CDA教材” 了解CDA考试详情；

▷ 想查询CDA考试成绩，点击>>> “CDA成绩” 了解CDA考试详情；

▷ 想了解CDA考试含金量，点击>>> “CDA含金量” 了解CDA考试详情；

▷ 想获取CDA考试时间/费用/条件/大纲/通过率，点击 >>>“CDA考试官网” 了解CDA考试详情；

python

数据分析咨询请扫描二维码

若不方便扫码，搜微信号：CDAshujufenxi

上一篇CDA认证再升一档！与国家共同推进大数据人才培养标准教育事业！
下一篇企业如何利用商品推荐的大数据来破除实体寒冰？
CDA考试动态
CDA报考指南
热门栏目
最新资讯
更多
Copyright © 2015-present 北京国富如荷网络科技有限公司 All Rights Reserved.
京ICP备11001960号-9   京公网安备 11010802034615号   经营许可证编号：京B2-20210330
客服在线
立即咨询