今天来总结一下常用的最短路径算法。符号简称:E -- # of edges; V -- # of vertexes
Single Source Shortest Path:
on non-weighted Graph: Bredth First Search
Non-Negative-Cylic Graph: Dikstra -- BFS + Priority Queue -- O(E) + O(V log V)
Graph With Negative Cycle: Bellman Ford's: Relax Node for N-1 times, then check if can still relax node (negative cycle)
Time Complexity: O(E * V)
还有国产的Shortest Path Faster Algorithm: 用一个队列记录当前relex的node。每次拿出要relex的node来继续relex。如果有一个node relex的次数超过了n次,那么说明有负环 —— O(kE),一般情况下k < 2。国产的东西就是好。
Minimum Spaning Tree:
Prim's -- O(E log V): 找当前点可见边中,连接没有visit过的点的最短的。
Kruskal's -- O(E log(E)) = O(E log(V)):首先Sort一下所有边。然后从weight最小的两条边一点点加点进来,直到包含了所有点。
All Pair Shortest Path:
Floyd Warshall (V^3): 只要记住这个recursive formula就会写code了:
define function: shortest(i,j,k) ==> the shortest path from node i to node j, only pass by element from set {1,...,k}
shortestPath(i,j,0) = w(i,j)
shortestPath(i,j,k) = min(shortestPath(i,j,k-1), shortestPath(i,k,k-1) + shortestPath(k,j,k-1))
分享到:
相关推荐
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
为了保证最后寻路的最短路径没错,附带一个ksp网络路由寻路算法(这个是网上找的)。自己跑的几个测试结果是没错的。 KSP算法使用方法: 在KSP-algorithm文件夹中,打开并运行gen_k_shortest_path.m,输出结果保存在...
旅行商问题(Traveling Salesman Problem,TSP)是一种著名的组合优化问题,涉及在给定的一组城市之间找到最短路径,确保旅行商能够经过每个城市一次,最终回到起点城市。本文将介绍旅行商问题的背景、问题特性和...
电子商务:通过收集用户消费习惯、季节和产品生命周期的数据,建立算法模型来确定下一个月、几个月甚至一年的消费者需求。这样可以提高订单转化率。在营销方面,可以给买家贴标签,建立人群画像,针对不同人群精准...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...