Python|【算法】python有向图中的最优路径 Python|python实践

给定有向图一起点S与顶点V，判断S与V之间是否存在路径，若有，找出最短的路径

# -*- coding: utf-8 -*- # /usr/bin/python # 作者：kimicr # 实验日期：20190322 # Python版本：3.6.3 # 给定有向图一起点S与顶点V，判断S与V之间是否存在路径，若有，找出最短的路径 # 分析：用广度优先搜索S到各个点的路径，再用深度优先搜索找到最短路径 from collections import deque class optimal_path(object): def __init__(self,Graph): self.Graph = Graph self.edgeTo = {} self.depth = 0 self.mark = [] for i in range(len(self.Graph)): self.mark.append(0) self.path = self.mark[:]def dfs(self,start,end): if start == end: self.path[self.depth] = int(start) return True if self.visited[str(start)] == 1: return False else: self.visited[str(start)] = 1 self.path[self.depth] = int(start) self.depth += 1 for i in self.new_edgeTo[str(start)]: if self.dfs(i,end) == True : return True self.depth -= 1 return Falsedef bfs(self, start, end):# 寻找起点为start的路径，并得到相应字典edgeTo self.visited = {} d = deque() d.append(int(start)) self.new_edgeTo = {} self.mark[int(start)] = 1#先把起点存入队列并标记 while d: person = d.popleft() for i in self.Graph[str(person)]:#判断该点的下一级元素 if self.mark[i] == 0:#如果没有访问 self.mark[i] = 1#则标记为1，视为现在已经访问 d.append(i)#并加入到队列中 self.edgeTo[str(i)] = int(person)#设置为主从顶点的关系 else: pass if start in self.edgeTo: del self.edgeTo[start]#删除存储到列表中输入的起点元素 #print('edgeTo=', self.edgeTo) for i in range(len(self.Graph)):# 准备一个新的数组，来存储到顶点S的最短路径 self.new_edgeTo[str(i)] = [] self.visited[str(i)] = 0#创建一个新的判断标志的字典for k, v in self.edgeTo.items():#把edgeTo中的数据转换形式并存入到new_edgeTo中 self.new_edgeTo[str(v)].append(int(k)) #print('new_edgTo=', self.new_edgeTo) self.dfs(start,end)#调用深度优先搜索 self.path = self.path[:self.depth+1] #print(self.path[:self.depth+1])#输出最短路径 print(self.path) if len(self.path[:self.depth + 1]) == 0: print("no path") else: print("path:",end='') for i in self.path[:self.depth]: print(i, end='-->') print(self.path[self.depth])if __name__ == "__main__": Graph = {'0':[5,1], '1':[], '2':[0,3], '3':[5,2], '4':[3,2], '5':[4], '6':[0,4,9], '7':[6,8], '8':[7,9], '9':[10,11], '10':[12], '11':[4,12], '12':[9], } g = optimal_path(Graph) g.bfs(8,4)

【Python|【算法】python有向图中的最优路径】结果：