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 -*-
class DijkstraExtendPath():
  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()
    return self._format_path()
  def _init_dijkstra(self):
    self.used_node_list.append(self.from_node)
    self.collected_node_dict[self.from_node] = [0, -1]
    for index1, node1 in enumerate(self.node_map[self.from_node]):
      if node1:
        self.collected_node_dict[index1] = [node1, self.from_node]
    self._foreach_dijkstra()
  def _foreach_dijkstra(self):
    if len(self.used_node_list) == self.node_length - 1:
      return
    for key, val in self.collected_node_dict.items(): # 遍历已有权值节点
      if key not in self.used_node_list and key != to_node:
        self.used_node_list.append(key)
      else:
        continue
      for index1, node1 in enumerate(self.node_map[key]): # 对节点进行遍历
        # 如果节点在权值节点中并且权值大于新权值
        if node1 and index1 in self.collected_node_dict and self.collected_node_dict[index1][0] > node1 + val[0]:
          self.collected_node_dict[index1][0] = node1 + val[0] # 更新权值
          self.collected_node_dict[index1][1] = key
        elif node1 and index1 not in self.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]))
    while self.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()
    return node_list
def set_node_map(node_map, node, node_list):
  for x, y, val in node_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 = [[0 for val in xrange(len(node))] for val in xrange(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)
  print path

运行结果:

再来一例:

<!-- lang: python -->
# -*- coding: utf-8 -*-
import itertools
import re
import math

def combination(lst):  #全排序
  lists=[]
  liter=itertools.permutations(lst)
  for lts in list(liter):
    lt=''.join(lts)
    lists.append(lt)
  return lists

def coord(lst):   #坐标输入
  coordinates=dict()
  print u'请输入坐标:(格式为A:7 17)'
  p=re.compile(r"\d+")
  for char in lst:
    str=raw_input(char+':')
    dot=p.findall(str)
    coordinates[char]=[dot[0],dot[1]]
  print coordinates
  return coordinates

def repeat(lst):  #删除重复组合
  for ilist in lst:
    for k in xrange(len(ilist)):
      st=(ilist[k:],ilist[:k])
      strs=''.join(st)
      for jlist in lst:
        if(cmp(strs,jlist)==0):
          lst.remove(jlist)
    for k in xrange(len(ilist)):
      st=(ilist[k:],ilist[:k])
      strs=''.join(st)
      for jlist in lst:
        if(cmp(strs[::-1],jlist)==0):
          lst.remove(jlist)
    lst.append(ilist)
    print lst
  return lst

def count(lst,coordinates): #计算各路径
  way=dict()
  for str in lst:
    str=str+str[:1]
    length=0
    for i in range(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
  return way

if __name__ =="__main__":
  print u'请输入图节点:'
  rlist=list(raw_input())
  coordinates=coord(rlist)

  list_directive = combination(rlist)
#  print "有方向完全图所有路径为:",list_directive
#  for it in list_directive:
#    print it
  print u'有方向完全图所有路径总数:',len(list_directive),"\n"

#无方向完全图
  list_directive=repeat(list_directive)
  list_directive=repeat(list_directive)
#  print "无方向完全图所有路径为:",list_directive
  print u'无方向完全图所有路径为:'
  for it in list_directive:
    print it
  print u'无方向完全图所有路径总数:',len(list_directive)

  ways=count(list_directive,coordinates)
  print u'路径排序如下:'
  for dstr in sorted(ways.iteritems(), key=lambda d:d[1], reverse = False ):
    print dstr
  raw_input()

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

请您花一点时间将文章分享给您的朋友或者留下评论。我们将会由衷感谢您的支持!

(0)

相关推荐

  • python简单猜数游戏实例

    本文实例讲述了python简单猜数游戏.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python import random number = random.randint(0,100) print "Hello,Number guessing Game: betwween 0 and 100 inclusive." guessString = raw_input("guess a number: ") guess = int(guess

  • python实现RSA加密(解密)算法

    RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准. 今天只有短的RSA钥匙才可能被强力方式解破.到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式.只要其密钥的长度足够长,用RSA加密的信息实际上是不能被解破的.但在分布式计算和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战. RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥.

  • python实现井字棋游戏

    本文实例介绍了python实现井字棋游戏的方法,分享给大家,具体内容如下 windows7下python3.4.0编译运行通过.由于采用了cmd调用,所以与Linux不兼容,无法在Linux下运行. 游戏就是井字棋,小键盘上的数字位置对应棋盘位置. #本游戏python3.4.0下编写调试,只能在windows下运行. import random import subprocess import time #定义函数 def draw_board(the_board): subprocess.c

  • python使用rsa加密算法模块模拟新浪微博登录

    PC登录新浪微博时,在客户端用js预先对用户名.密码都进行了加密,而且在POST之前会GET一组参数,这也将作为POST_DATA的一部分.这样,就不能用通常的那种简单方法来模拟POST登录(比如人人网). 通过爬虫获取新浪微博数据,模拟登录是必不可少的. 1.在提交POST请求之前,需要GET获取四个参数(servertime,nonce,pubkey和rsakv),不是之前提到的只是获取简单的servertime,nonce,这里主要是由于js对用户名.密码加密方式改变了. 1.1 由于加密

  • Python贪吃蛇游戏编写代码

    最近在学Python,想做点什么来练练手,命令行的贪吃蛇一般是C的练手项目,但是一时之间找不到别的,就先做个贪吃蛇来练练简单的语法. 由于Python监听键盘很麻烦,没有C语言的kbhit(),所以这条贪吃蛇不会自己动,运行效果如下: 要求:用#表示边框,用*表示食物,o表示蛇的身体,O表示蛇头,使用wsad来移动 Python版本:3.6.1 系统环境:Win10 类: board:棋盘,也就是游戏区域 snake:贪吃蛇,通过记录身体每个点来记录蛇的状态 game:游戏类 本来还想要个foo

  • 一步步教你用Python实现2048小游戏

    前言 2048游戏规则:简单的移动方向键让数字叠加,并且获得这些数字每次叠加后的得分,当出现2048这个数字时游戏胜利.同时每次移动方向键时,都会在这个4*4的方格矩阵的空白区域随机产生一个数字2或者4,如果方格被数字填满了,那么就GameOver了. 主逻辑图 逻辑图解:黑色是逻辑层,蓝色是外部方法,红色是类内方法,稍后即可知道~ 下面容我逐行解释主逻辑main()函数,并且在其中穿叉外部定义的函数与类. 主逻辑代码解读(完整代码见文末) 主逻辑main如下,之后的是对主函数中的一些方法的解读

  • Python外星人入侵游戏编程完整版

    PYTHON游戏编程外星人入侵的完整实现思路,具体内容如下 准备工作:下载python,比如Anaconda3(64 bit),导入pygame游戏包 1.外星人设置,alien.py,代码: import pygame from pygame.sprite import Sprite class Alien(Sprite): """表示单个外星人的类""" def __init__(self,ai_settings,screen): "

  • Python使用pygame模块编写俄罗斯方块游戏的代码实例

    文章先介绍了关于俄罗斯方块游戏的几个术语. 边框--由10*20个空格组成,方块就落在这里面. 盒子--组成方块的其中小方块,是组成方块的基本单元. 方块--从边框顶掉下的东西,游戏者可以翻转和改变位置.每个方块由4个盒子组成. 形状--不同类型的方块.这里形状的名字被叫做T, S, Z ,J, L, I , O.如下图所示: 模版--用一个列表存放形状被翻转后的所有可能样式.全部存放在变量里,变量名字如S_SHAPE_TEMPLATE or J_SHAPE_TEMPLATE 着陆--当一个方块

  • Python实现的弹球小游戏示例

    本文实例讲述了Python实现的弹球小游戏.分享给大家供大家参考,具体如下: 弹球 1. Ball 类 draw负责移动Ball 碰撞检测,反弹,Ball检测Paddle 2.Paddle类 draw负责移动Paddle 碰撞检测,确定能不能继续 监听键盘事件 3.主循环 绘制Ball和Paddle update sleep 代码 from Tkinter import * import random import time class Ball: def __init__(self, canv

  • Python实现破解猜数游戏算法示例

    本文实例讲述了Python实现破解猜数游戏算法.分享给大家供大家参考,具体如下: QQ群里的聊天机器人会发起猜数小游戏. 玩法如下: 1. 用户发 #猜数    到群里 2. 机器人响应: 猜数已经开始, 范围是1-10000之间的某个数 3. 你发送 #猜数[123] 到群里 4. 机器人响应: 大了或者小了, 或者恭喜你猜中了 5. 你根据刚才猜的123, 和返回, 猜一个更小或更大的数, 发送 #猜数[111] , 即返回第2步 那么最好的猜测方法肯定是找居中的数了, 由于心算耗时, 所以

  • python实现的生成随机迷宫算法核心代码分享(含游戏完整代码)

    完整代码下载:http://xiazai.jb51.net/201407/tools/python-migong.rar 最近研究了下迷宫的生成算法,然后做了个简单的在线迷宫游戏.游戏地址和对应的开源项目地址可以通过上面的链接找到.开源项目中没有包含服务端的代码,因为服务端的代码实在太简单了.下面将简单的介绍下随机迷宫的生成算法.一旦理解后你会发现这个算法到底有多简单. 1.将迷宫地图分成多个房间,每个房间都有四面墙. 2.让"人"从地图任意一点A出发,开始在迷宫里游荡.从A房间的1/

  • python k-近邻算法实例分享

    简单说明 这个算法主要工作是测量不同特征值之间的距离,有个这个距离,就可以进行分类了. 简称kNN. 已知:训练集,以及每个训练集的标签. 接下来:和训练集中的数据对比,计算最相似的k个距离.选择相似数据中最多的那个分类.作为新数据的分类. python实例 复制代码 代码如下: # -*- coding: cp936 -*- #win系统中应用cp936编码,linux中最好还是utf-8比较好.from numpy import *#引入科学计算包import operator #经典pyt

随机推荐