python实现Floyd算法
作者:通信程序猿 发布时间:2021-08-09 16:17:52
标签:python,Floyd,算法
下面是用Python实现Floyd算法的代码,供大家参考,具体内容如下
# -*- coding: utf-8 -*-
"""
Created on Thu Jul 13 14:56:37 2017
@author: linzr
"""
## 表示无穷大
INF_val = 9999
class Floyd_Path():
def __init__(self, node, node_map, path_map):
self.node = node
self.node_map = node_map
self.node_length = len(node_map)
self.path_map = path_map
self._init_Floyd()
def __call__(self, from_node, to_node):
self.from_node = from_node
self.to_node = to_node
return self._format_path()
def _init_Floyd(self):
for k in range(self.node_length):
for i in range(self.node_length):
for j in range(self.node_length):
tmp = self.node_map[i][k] + self.node_map[k][j]
if self.node_map[i][j] > tmp:
self.node_map[i][j] = tmp
self.path_map[i][j] = self.path_map[i][k]
print '_init_Floyd is end'
def _format_path(self):
node_list = []
temp_node = self.from_node
obj_node = self.to_node
print("the shortest path is: %d")%(self.node_map[temp_node][obj_node])
node_list.append(self.node[temp_node])
while True:
node_list.append(self.node[self.path_map[temp_node][obj_node]])
temp_node = self.path_map[temp_node][obj_node]
if temp_node == obj_node:
break;
return node_list
def set_node_map(node_map, node, node_list, path_map):
for i in range(len(node)):
## 对角线为0
node_map[i][i] = 0
for x, y, val in node_list:
node_map[node.index(x)][node.index(y)] = node_map[node.index(y)][node.index(x)] = val
path_map[node.index(x)][node.index(y)] = node.index(y)
path_map[node.index(y)][node.index(x)] = node.index(x)
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[i][j] 存储i到j的最短距离
node_map = [[INF_val for val in xrange(len(node))] for val in xrange(len(node))]
## path_map[i][j]=j 表示i到j的最短路径是经过顶点j
path_map = [[0 for val in xrange(len(node))] for val in xrange(len(node))]
## set node_map
set_node_map(node_map, node, node_list, path_map)
## select one node to obj node, e.g. A --> D(node[0] --> node[3])
from_node = node.index('A')
to_node = node.index('E')
Floydpath = Floyd_Path(node, node_map, path_map)
path = Floydpath(from_node, to_node)
print path
运行结果为:
the shortest path is: 23
['A', 'F', 'G', 'C', 'E']
来源:http://blog.csdn.net/u011285477/article/details/75096303
0
投稿
猜你喜欢
- python通过安装使用paramiko模块,将本地文件上传到服务器上import paramikoimport datetimeimpor
- 相关验证码文章:asp制作验证码的方法 轩魂ASP中文验证码下载 先产生一个4位数的随机码源代码:ychar="0,1,2,3,4
- 相关概念并发:指一个时间段内,有几个程序在同一个cpu上运行,但是任意时刻只有一个程序在cpu上运行。比如说在一秒内cpu切换了100个进程
- 01直接生成这类方法是利用基本程序软件包numpy的随机数产生方法来生成各类用于聚类算法数据集合,也是自行制作轮子的生成方法。一、基础类型1
- 本文实例讲述了Python上下文管理器类和上下文管理器装饰器contextmanager用法。分享给大家供大家参考,具体如下:一. 什么是上
- 如下所示:#coding=utf-8#布局自定义尺寸from tkinter import *class App:def __init__(
- 对于初学者来说,一份详尽又清晰明白的指南很重要。今天,猫猫跟大家一起,好好学习Python文件读写的内容,这部分内容特别常用,掌握后对工作和
- 包的引入:import numpy as npimport pandas as pd1. Series 对象的创建1.1 创建一个空的 Se
- 我的PJBlog在从2.7升级的3.0的时候,犹豫了很久。升级到PJBlog3.0就是看中了新增的静态页面功能,但是同时又担心造成博客出现大
- 在使用Tensorflow的过程中,我们经常遇到数组形状不同的情况,但有时候发现二者还能进行加减乘除的运算,在这背后,其实是Tensorfl
- 我的同事Fara给大家介绍了戴尔网站首页的改版设计,这里我还想和大家介绍一下戴尔是如何从网站用户使用体验的角度进行设计,让大家进一步了解戴尔
- 用python另一个抢票神器,你get到了吗?2017年时间飞逝,转眼间距离2018年春节还有不到1个月的时间,还在为抢不到火车票发愁吗?作
- 以XML格式查看查询结果通过使用传统—xml 选项调用MySQL命令行客户程序,你可以以XML格式(而不是传统的列表形式
- 基于flask的web应用的诞生,供大家参考,具体内容如下Flask是一个非常优秀的web框架,它最大的特点就是保持一个简单而易于扩展的小核
- 项目场景:使用Anaconda Prompt创建虚拟环境问题描述保存虚拟环境的默认地址是C盘,而我想将下载的虚拟环境保存到我自定义的位置。解
- 这个是JS控制图片滚动的效果,当鼠标结果新闻标题时开始滚动到对应的图片,可以作为图片新闻。效果图:<!DOCTYPE HTML PUB
- 1 前言前面的文章中我们已经获取到了基金的阶段变动信息和ETF信息的获取,那么在本章中,我们将继续前面的内容,获取基金的价格信息,并且把之前
- 需要安装pyechartspip install pyecharts -U 创建【demo6.py】并输入以下编码:from py
- 引用计数Python 语言默认采用的垃圾收集机制是『引用计数法 Reference Counting』,该算法最早 George E. Co
- 人的大脑通过双眼来辨别视觉图形获取信息。大脑根据储存的经验,将所看到的视觉图形建立起优先级。由此可见,一个良好的视觉设计可以帮助大脑迅速有效