介绍
1. 最短路算法
最短路算法是一类用于在加权有向图中搜索从起点到终点最短路径(或距离)的算法。其中最为经典的算法为 Dijkstra 和 Bellman-Ford 算法,分别适用于没有负权边和存在负权边的情况。此外,还有 Floyd-Warshall 算法,它适用于解决所有节点对之间的最短路问题。最短路算法在计算机网络、路径规划、交通流量控制等领域有着广泛应用。其实还有A*算法,只不过那个在游戏领域用的比较多
2. 网络流算法
网络流算法是用于解决最大流和最小割问题的一种算法家族。最经典的算法有 Ford-Fulkerson 算法和 Edmonds-Karp 算法,它们都使用了增广路思想来不断增加流量,直到达到最大流或最小割。网络流算法广泛应用于资源分配、流量控制、匹配问题等领域。
3. 二分图算法
二分图算法是一类用于处理二分图的算法,其中包括最大匹配、最小点覆盖和最大独立集等问题。常见的算法包括 Hopcroft-Karp 算法、匈牙利算法、KM 算法等。二分图算法主要应用于稳定婚姻问题、职工情感调配问题、数据匹配等领域。