当前位置:   article > 正文

机器学习——最短路径算法_基于机器学习的最短路径搜索系统

基于机器学习的最短路径搜索系统

理论

使用字典的方式构建有向图,并搜索图中的路径。
提供了三种不同的操作函数:
不足点:只能够处理无权无向图

代码实现

#这个图有6个节点(A-G)和8个弧。它可以通过下面的Python数据结构来表示:
graph = {'A': ['B', 'C','D'],
         'B': ['E'],
         'C': ['D','F'],
         'D': ['B','E','G'],
         'E': [],
         'F': ['D','G'],
         'G': ['E']}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
# 找到一条从start到end的路径
def findPath(graph,start,end,path=[]):   
    path = path + [start]
    if start == end:
        return path 
    for node in graph[start]:
        if node not in path:
            newpath = findPath(graph,node,end,path)
            if newpath:
                return newpath
    return None
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
# 找到所有从start到end的路径
def findAllPath(graph,start,end,path=[]):
    path = path +[start]
    if start == end:
        return [path]
 
    paths = [] #存储所有路径    
    for node in graph[start]:
        if node not in path:
            newpaths = findAllPath(graph,node,end,path) 
            for newpath in newpaths:
                paths.append(newpath)
    return paths
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

# 查找最短路径
def findShortestPath(graph,start,end,path=[]):
    path = path +[start]
    if start == end:
        return path
    
    shortestPath = []
    for node in graph[start]:
        if node not in path:
            newpath = findShortestPath(graph,node,end,path)
            if newpath:
                if not shortestPath or len(newpath)<len(shortestPath):
                    shortestPath = newpath
    return shortestPath
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
onepath = findPath(graph,'A','G')
print('一条路径:',onepath)
 
allpath = findAllPath(graph,'A','G')
print('\n所有路径:',allpath)
 
shortpath = findShortestPath(graph,'A','G')
print('\n最短路径:',shortpath)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/550219
推荐阅读
相关标签
  

闽ICP备14008679号