数学建模图论算法学习总结
数学建模图论算法学习总结
图论基本知识
B站视频： 图论中的圈与块：
一、Dijkstra& Floyd求解最短路径
1.1 Dijkstra (MATLAB C#)
采用贪心算法（Greedy Algorithm）范式进行设计 B站MATLAB实现： C#实现：
1.2 Floyd (MATLAB) Bellman-Ford
用于计算带权有向图中单源最短路径。 采用动态规划（Dynamic Programming）进行设计 B站MATLAB实现： 总结：到问题，转化为带权邻接矩阵，然后输入程序。数学建模时可以用不同算法比较分析，更有说服力。
二、Kruskal& Prim求解最小生成树
B站视频，讲的特别好！
2.1最小生成树
生成树： i. 不能有环 ii. 必须连接图中的全部顶点 所以最小生成树的任意两个顶点之间可以连通，对于有N个顶点的树，其边的个数为N-1。 最小生成树： 对于一个图，可以有很多生成树，边的权值相加最小的就是最小生成树。 应用： 如几个城市之间铺设光缆，按最小生成树铺设，就可以实现几个城市之间都能连通，所需成本又最小。
2.2 Kruskal
2.3 Prim
三、最大流
管道网络中每条边的最大通过能力（容量）是有限的，实际流量不超过容量。 最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。 基本概念： 算法：FF算法、EK算法、dinic算法 EK算法：BFS找增广路 dinic算法
四、二分匹配，匈牙利算法
二分图 找增广路
