知行编程网知行编程网  2022-10-09 21:30 知行编程网 |  隐藏边栏 |  72 
文章评分 0 次，平均分 0.0 ：
导语： 本文主要介绍了关于如何用python实现最短路径的相关知识，包括python算法大全，以及最短路径迪杰斯特拉算法这些编程知识，希望对大家有参考作用。

python中最短路径的实现方法： 1. Dijkstra算法：声明一个数组dis来保存源点到每个顶点的最短距离； 2、弗洛伊德算法：求解有向图中点与点之间的关系。 3、SPFA算法：用数组dis记录每个节点的最短路径的估计值。

如何用python实现最短路径

最短路径问题（python实现）

解决最短路径问题：（如下三种算法）

（1）迪杰斯特拉算法（Dijkstra算法）

（2）弗洛伊德算法（Floyd算法）

（3）SPFA算法



第一种算法：

Dijkstra算法

广度优先搜索解决了加权有向或无向图的单源最短路径问题。这是一个贪婪的策略

算法的思路

声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，

初始时，原点s的路径权重被赋为0（dis[s]=0）。若对于顶点s存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,

同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，

再看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，

如果是，那么就替换这些顶点在dis中的值，然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。



第二种算法：


Floyd算法

原理：

Floyd算法（弗洛伊德算法）是一种在有向图中求最短路径的算法。它是一种求解有向图中点与点之间最短路径的算法。

用在拥有负权值的有向图中求解最短路径（不过不能包含负权回路）

流程：

有向图中的每一个节点X，对于图中过的2点A和B，

如果有Dis（AX）+ Dis（XB）< Dis（AB），那么使得Dis（AB）=Dis（AX）+Dis（XB)。

当所有的节点X遍历完后，AB的最短路径就求出来了。

示例一： 

 #-*- coding:utf-8 -*-
 #python实现Floyd算法
 
N = 4 
_=float('inf')      #无穷大 
 graph = [[ 0, 2, 6, 4],[ _, 0, 3, _],[ 7, _, 0, 1],[ 5, _,12, 0]] 
 path = [[-1,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,-1,-1]]        #记录路径，最后一次经过的点
def back_path(path,i,j):            #递归回溯
while(-1 != path[i][j]):
     back_path(path,i,path[i][j])
       back_path(path,path[i][j],j)
      print path[i][j],14        
 return;
   return;
print "Graph:\n",graph
for k in range(N):
  for i in range(N):
      for j in range(N):
            if graph[i][j] > graph[i][k] + graph[k][j]:
             graph[i][j] = graph[i][k] + graph[k][j]
            path[i][j] = k
 print "Shortest distance:\n",graph
 print "Path:\n",path
 print "Points pass-by:"
 for i in range(N):
  for j in range(N):
      print "%d -> %d:" % (i,j),
       back_path(path,i,j)
        print "\n",

示例二： 

#!usr/bin/env python#encoding:utf-8
'''
功能：使用floyd算法求最短路径距离
'''
import random
import time
def random_matrix_genetor(vex_num=10):    
    '''
    随机图顶点矩阵生成器
    输入：顶点个数，即矩阵维数    
    '''
    data_matrix=[]    
    for i in range(vex_num):
        one_list=[]        
        for j in range(vex_num):
            one_list.append(random.randint(1, 100))
        data_matrix.append(one_list)    
        return data_matrixdef floyd(data_matrix):    
        '''
    输入：原数据矩阵，即：一个二维数组
    输出：顶点间距离    '''
    dist_matrix=[]
    path_matrix=[]
    vex_num=len(data_matrix)  
    for h in range(vex_num):
        one_list=['N']*vex_num
        path_matrix.append(one_list)
        dist_matrix.append(one_list)    
    for i in range(vex_num):        
        for j in range(vex_num):
            dist_matrix=data_matrix
            path_matrix[i][j]=j    
    for k in range(vex_num):        
        for i in range(vex_num):            
            for j in range(vex_num):                
                if dist_matrix[i][k]=='N' or dist_matrix[k][j]=='N':
                    temp='N'
                else:
                    temp=dist_matrix[i][k]+dist_matrix[k][j]                
                if dist_matrix[i][j]>temp:
                    dist_matrix[i][j]=temp
                    path_matrix[i][j]=path_matrix[i][k]    
    return dist_matrix, path_matrixdef main_test_func(vex_num=10):    
     '''
     主测试函数
     '''
    data_matrix=random_matrix_genetor(vex_num)
    dist_matrix, path_matrix=floyd(data_matrix)    
    for i in range(vex_num):        
    for j in range(vex_num):            
    print '顶点'+str(i)+'----->'+'顶点'+str(j)+'最小距离为:', dist_matrix[i][j]
if __name__ == '__main__':
    data_matrix=[['N',1,'N',4],[1,'N',2,'N'],['N',2,'N',3],[4,'N',3,'N']]
    dist_matrix, path_matrix=floyd(data_matrix)    
    print dist_matrix    
    print path_matrix
 
    time_list=[] 
    print '------------------------------节点数为10测试情况------------------------------------'
    start_time0=time.time()
    main_test_func(10)
    end_time0=time.time()
    t1=end_time0-start_time0
    time_list.append(t1)    
    print '节点数为10时耗时为：', t1 
    print '------------------------------节点数为100测试情况------------------------------------'
    start_time1=time.time()
    main_test_func(100)
    end_time1=time.time()
    t2=end_time1-start_time1
    time_list.append(t2)    
    print '节点数为100时耗时为：', t2 
    print '------------------------------节点数为1000测试情况------------------------------------'
    start_time1=time.time()
    main_test_func(1000)
    end_time1=time.time()
    t3=end_time1-start_time1
    time_list.append(t3)    
    print '节点数为100时耗时为：', t3 
    print '--------------------------------------时间消耗情况为：--------------------------------'
    for one_time in time_list:        
    print one_time

示例三： 

import numpy as np
Max     = 100
v_len   = 4
edge    = np.mat([[0,1,Max,4],[Max,0,9,2],[3,5,0,8],[Max,Max,6,0]])
A       = edge[:]
path    = np.zeros((v_len,v_len)) 
 
def Folyd():    
    for i in range(v_len):        
        for j in range(v_len):            
            if(edge[i,j] != Max and edge[i,j] != 0):
                path[i][j] = i 
    print 'init:'
    print A,'\n',path    
    for a in range(v_len):        
        for b in range(v_len):            
            for c in range(v_len):                
                if(A[b,a]+A[a,c]<A[b,c]):
                    A[b,c] = A[b,a]+A[a,c]
                    path[b][c] = path[a][c]    
    print 'result:'            
    print A,'\n',path                
 
if __name__ == "__main__":
    Folyd()



第三种算法：

SPFA 算法是解决单源最短路径问题的算法，由 Richard Bellman 和 Lester Ford 创立。有时该算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为该算法的发展做出了贡献。它的原理是对图进行V-1松弛操作，得到所有可能的最短路径。

它相对于 Dijkstra 算法的优势是边的权重可以为负，实现简单。缺点是时间复杂度太高，高达O(VE)。但是，该算法可以通过多种方式进行优化以提高效率。

思路：

我们使用数组dis来记录每个节点的最短路径估计，并使用邻接表或邻接矩阵来存储图G。我们采用的方法是动态逼近法：设置一个先进先出队列最多存储需要优化的节点，优化时每次取出队列的第一个节点u，使用点u当前的最短路径估计值离开点u。指向的节点 v 进行松弛操作。如果调整了点v的最短路径估计值，并且点v不在当前队列中，则将点v放在队列的末尾。这样，节点就会不断地从队列中移除，进行松弛操作，直到队列为空。

python

本文为原创文章，版权归所有，欢迎分享本文，转载请保留出处！

知行编程网
知行编程网 关注：1    粉丝：1
这个人很懒，什么都没写

你可能也喜欢

热评文章

上一篇
下一篇
扫一扫二维码分享
 繁