阿里邮箱企业版官网,网站做优化需要哪些后台信息,济南源聚网络公司,建设工程合同印花税税率明天就要面试了我也太紧张了吧
但是终于找到了一个比较好理解的dijkstra的python解法#xff0c;让我快点把它背下来#xff01;#xff01;#xff01;#xff01; 文章目录 题目dijkstra算法的python实现python解答dfs解法dijkstra解法 题目
先把题目放出来 某通信网络…明天就要面试了我也太紧张了吧
但是终于找到了一个比较好理解的dijkstra的python解法让我快点把它背下来 文章目录 题目dijkstra算法的python实现python解答dfs解法dijkstra解法 题目
先把题目放出来 某通信网络中有N个网络结点用1到N进行标识。网络通过一个有向无环图表示其中题的边的值表示结点之间的消息传递时延。现给定相连节点之间的时延列表 times[i] {u,v,w},其中u表示源节点v表示目的节点w表示u和v之间的消息传递时延。 请计算给定源结点到目的结点的最小传输时延如果目的结点不可达返回-1。 输入描述 输入的第一行为两个正整数分别表示网络结点的个数N以及时延列表长度M用空格分隔。 接下来的M行为两个结点间的时延列表[u,v,w] 输入的最后一行为两个正整数分别表示源结点和目的结点。
比如
输入3 3 1 2 11 2 3 13 1 3 50 1 3 输出24
一个有向无环图用dfs也很好做。这里我们重点看一下dijkstra怎么做。
dijkstra算法的python实现
最短路径算法Dijkstra主要思想是贪心。每次遍历到始点距离最近且未访问过的顶点的邻接节点直到扩展到终点为止。 更具体地来说 假设我们现在在一个有权图中图中有n个点点与点相连的路径上都分配有权重代表了两点之间的距离。现在有一个起始点i终点j如果求i到j的最短距离。
我们建立一个集合s把起始点i放进去然后在与i相邻的边中寻找与i距离最近的点并把这个点放到集合中去。然后第二次遍历与集合中的点相连的点并更新到起始点的距离并把距离起始点i最近的点放到集合中去。继续上面的做法每次都在集合中添加一个点。直到没有新的点可以添加进去。
我们来写一个比较简单的python实现。 假设现在有n个节点同时有一个输入distance距离列表里面的元素表示的是[u,v,w]即u到v的距离。现在给定起点k求k到最远的点的最小距离
dist [float(inf)]*n # 构建一个列表存放n个结点到目标k的距离
dist[k-1] 0 # 第k个结点到他本身的距离为0g [[float(inf)] * n for _ in range(n)] # 构建一个矩阵表示n个结点彼此的距离。
for x, y, dis in distance:g[x-1][y-1] time # 按照distance列表更新矩阵中两两结点的距离。used [False]*n # 判断点是否已经加入了set里面。for _ in range(n):x -1for y, u in enumerate(used):if not u and (x -1 or dist[y] dist[x]): #只考虑没有使用过的节点寻找结点们到初始点的最小距离。# 毫无疑问在第一次遍历中这个距离是0目标点是我们的源点本身。x y # 如果距离小就用新的点替换掉x。used[x] True # 每次都使用距离源点最近的点for y, time in enumerate(g[x]):dist[y] min(dist[y], dist[x]time) # 更新相连的结点到源点的距离ans max(dist) # 这就是我们要求的k到最远的点的最小距离dijkstra的时间复杂度是 O ( N 2 ) O(N^2) O(N2).
这个题也可以用dfs的方法来作遍历到父结点时更新所有的子结点到源点的距离。dfs解该题的时间复杂度更高一点是 O ( N N ) O(N^N) O(NN). 同样给出一个解法代码。
map_dict defaultdict(list)
for u, v, w in distance:map_dict[u].append([v,w]) dist [float(inf)] * n
def dfs(index, dis):if dis dist[index-1]:dist[index-1] disfor v, w in map_dict[index]:dfs(v,disw)
dfs(k,0)res max(dist)python解答
我们回到题目的python解答上。
dfs解法
首先我们给出一个dfs的解答。 可以看到这个解法和上面的dfs几乎一模一样区别是这里返回的是源节点到目标点的距离。
def solution(times,src, dist):graph {}for u,v, w in times:if u not in graph:graph[u] []graph[u].append([v,w])root [float(inf)]*N def dfs(index, dis):if disroot[index-1]:root[index-1] disif index in graph:for u, v in graph[index]:dfs(u,disv)dfs(src,0)res root[dist-1]return res if res!float(inf) else -1
dijkstra解法
这个解法也是和上面的思路一样只不过在发现xdis-1的时候提前break结束了这个循环。
def solution(times, src, dis):g [[float(inf)]*N for _ in range(N)]for u,v, time in times:g[u-1][v-1] timedist [float(inf)]*Ndist[src-1] 0used [False]*Nfor i in range(N):x -1for y, u in enumerate(used):if not u and (x-1 or dist[y] dist[x]):x yif x dis-1:breakused[x] Truefor y, time in enumerate(g[x]):dist[y] min(dist[y],dist[x]time)return dist[dis-1]
