Floyd算法

2021/12/19 14:49:52

本文主要是介绍Floyd算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

  • 解释
    • 核心思想
    • 具体操作
      •   一、首先我们需要准备两个数组A,path
      •   二、开始操作A,path*
      •   三、输出路径
  • 全部代码

解释


核心思想

  当一个结点到达另一个结点时,是否存在一个中间结点,使其转折到达的距离小于直接到达的距离


具体操作

  一、首先我们需要准备两个数组A,path

  - - 两个矩阵的大小均由数据的个数(结点数量)决定,且均为方阵 - -

  A作为邻接矩阵,也就是说A是根据题意得到的一个矩阵,只考虑当前数据(结点u,v)是否可以直达,直达则对A中u行v列中的数据进行初始化,且值为题中所提供的的值。最后A中未初始化的值,皆为无法互相直达的结点,因此任取一个无穷大的值(不要影响运算,尽量取到大多数值的更高量级)来初始化这个结点值,表示无法直接到达。
  path为辅助矩阵,目的是记录所有的中间结点。他是在对A处理结束之后,
记录所有路径的矩阵。权值则需A一起求解

事例:

邻接矩阵A:

在这里插入图片描述

path矩阵:

在这里插入图片描述


  二、开始操作A,path*

  体现核心思想的主要地方。具体解释就是核心思想。

for k in range(len(list)): #中间结点
	#每个结点作为中间结点,判断对结点互达距离的的大小
    for i in range(len(list)):
        for j in range(len(list)):
            #每个结点到达自身的距离肯定最短,判断无意义
            if (i==j or i==k or k==j):
                continue;
            if(list[i][j]>list[i][k]+list[k][j]):
                list[i][j]=list[i][k]+list[k][j] #修改权重
                path[i][j]=k #修改中间结点
                

处理之后的 path 数组
在这里插入图片描述


处理之后的 邻接矩阵A

在这里插入图片描述


  三、输出路径

  其实就是一个递归的过程。例如 u = 0;v = 3;求出0->3的最短路径
根据处理之后的 path 数组判断第 u 行,第 v 列是否等于 -1 如果是,则表示两点可直达直接输出。

  if path[n][p] == -1:
       print("<",u,",",v,">")

  如果不是 -1 则表示两点直接存在跟短路径,且此时的值正好是最短路径下的下一个结点,我们只需要知道当前起点到这个点,再由这个点作为新的起始节点去寻找到达终点结点的最短路径

	mid= path[n][p]       #记录中间结点
    priFloyd(n,mid,path)  #去寻找当前起始节点到中间结点的最短路径
    priFloyd(mid,p,path)  #去寻找中间结点到目的终点的最短路径

结果为:
在这里插入图片描述

全部代码

import numpy as np
import pandas as pd
inf = 1000000
list = [0,5,inf,7,inf,0,4,2,3,3,0,2,inf,inf,1,0]
path = []
for i in range(4):
    for j in range(4):
        path.append(-1)

list = pd.DataFrame(np.array(list).reshape(4,4))
path = pd.DataFrame(np.array(path).reshape(4,4,))
for k in range(len(list)):
    for i in range(len(list)):
        for j in range(len(list)):
            if (i==j or i==k or k==j):
                continue;
            if(list[i][j]>list[i][k]+list[k][j]):
                list[i][j]=list[i][k]+list[k][j]
                path[i][j]=k

print(path)
print(list)

def priFloyd(n,p,path):
    if path[n][p] == -1:
        print("<",n,",",p,">")
    else:
        mid= path[n][p]
        priFloyd(n,mid,path)
        priFloyd(mid,p,path)

print("____________")
priFloyd(0,3,path)





这篇关于Floyd算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程