怎么开发个人网站,wordpress适合seo,网络推广学校培训,深圳 汽车网站建设弗洛伊德算法#xff1a;
弗洛伊德算法本质是动态规划#xff0c;通过添加点进如可选择的点组成的集合的同时更新所有点之间的距离#xff0c;从而得到每两个点之间的最短距离。 初始化#xff1a; 创建一个二维数组 dist#xff0c;其中 dist[i][j] 表示从节点 i 到节点…弗洛伊德算法
弗洛伊德算法本质是动态规划通过添加点进如可选择的点组成的集合的同时更新所有点之间的距离从而得到每两个点之间的最短距离。 初始化 创建一个二维数组 dist其中 dist[i][j] 表示从节点 i 到节点 j 的最短路径的权重。将对角线上的元素初始化为0表示节点到自身的距离。如果存在直接相连的边则将 dist[i][j] 初始化为这些边的权重否则初始化为一个大数表示无穷大。 三重循环 对于每一对节点 (i, j)以及所有可能的中间节点 k进行三重循环 plaintextCopy code for k from 1 to n: for i from 1 to n: for j from 1 to n: dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]) 在每一次迭代中检查是否通过中间节点 k 能够获得更短的路径。如果 dist[i][k] dist[k][j] 小于当前已知的 dist[i][j]则更新 dist[i][j]。 输出结果 算法结束后矩阵 dist 中的元素即为图中所有节点对之间的最短路径。 迪杰斯特拉算法
迪杰斯特拉算法是广度优先遍历算法的一种遍历当前节点的所有邻接点更新原点到邻接点的距离。最终得到原点到每个点的最小距离。 初始化 创建两个数组distance 和 visited。distance 数组用于存储从起始节点到各个节点的当前最短路径长度初始时将起始节点到自身的距离设置为0其他节点的距离设置为无穷大。visited 数组用于标记节点是否已经被访问初始时所有节点都未被访问。 选择起始节点 将起始节点标记为当前的工作节点。 更新邻接节点的距离 遍历当前工作节点的所有邻接节点计算从起始节点经过当前工作节点到邻接节点的路径长度。如果这个路径长度小于 distance 数组中记录的邻接节点的当前最短路径长度则更新 distance 数组。 选择下一个工作节点 从未访问的节点中选择一个具有最小最短路径长度的节点将其标记为当前的工作节点。如果所有未访问的节点都具有无穷大的最短路径长度说明剩下的节点不可达算法结束。 重复步骤3和4 重复执行步骤3和步骤4直到所有节点都被访问过。 案例题目
现在小丽在城镇A小明在城镇B。小丽要出发找小明。
城镇之间有双向通行的道路通过道路要消耗一定的时间。
其中已知城镇C和城镇D之间有双向的传送门可以不消耗时间瞬间传送过去
现在请你求出小丽从城镇A抵达城镇B的最短时间。保证从起点到终点有路径可达。
输入描述
第一行两个正整数n,m以空格分开表示总共有n个城镇有m条道路相连
第二行两个正整数A,B以空格分开分别表示小丽所在城镇A小明所在城镇B。
第三行两个正整数CD以空格分开表示城镇C和城镇D之间有瞬间的双向传送门。
接下来m行每行三个正整数u,v, c以空格分开表示城镇u和城镇v之间有道路通过道路消耗时间c。
对于100%的数据保证 1n 100,1m2*n每条道路的时间花费在[1,10]之间输出描述
一行一个整教表示最短到达时间。
样例输入
4 3
1 4
1 3
1 2 1
2 3 1
2 4 1样例输出
2
代码
弗洛伊德算法
n,m map(int,input().split( ))
A,B map(int,input().split( ))
print(A,B)
C,D map(int,input().split( ))
dis [[float(inf) for i in range(n1)] for j in range(n1)]
for i in range(m):u,v,c map(int,input().split( ))dis[u][v] cdis[v][u] cdis[C][D] dis[D][C] 0for k in range(1,n1):for i in range(1,n1):for j in range(1,n1):dis[i][j] min(dis[i][j],dis[i][k]dis[k][j])print(dis[A][B])
迪杰斯特拉算法
import collectionsn,m map(int,input().split( ))
A,B map(int,input().split( ))
C,D map(int,input().split( ))graph [[] for _ in range(n)]
for i in range(m):u,v,c map(int,input().split( ))graph[u-1].append((v-1,c))graph[v- 1].append((u-1,c))graph[C-1].append((D-1,0))
graph[D-1].append((C-1,0))def dijkstra(graph,start,end):n len(graph)distances [float(inf) for i in range(n)]distances[start] 0queue collections.deque( [(0,start)])vis [False] * nwhile queue:current_distance,current_node queue.popleft();if vis[current_node]:continuevis[current_node] Truefor neighbor,weight in graph[current_node]:new_distance current_distance weightif new_distance distances[neighbor]:distances[neighbor] new_distancequeue.append((new_distance,neighbor))return distances[end]print(dijkstra(graph,A-1,B-1))
