题纲:
1. 几种常见算法 适用场景。 区分有向图和无向图吗? no,都一样
2. 算法原理 基于什么思路。这门课讲实现,不讲原理。主要考察
3. Dijistra算法 实现思路。 模拟 稀疏图-邻接表。稠密图-邻接矩阵
4. 代码中 1重边 自环 2图中点的存储
5.
bellmanford算法
1 松弛操作 三角不等式
2 若有负权回路 就会最短路是负无穷 不存在最短路
bf算法可以判断是否有负环,抽屉原理 但一般用spfa算法 迭代k次,就是不超过k条边的最短路。若迭代n次,存在一条路径,上面有n条边,因为有n个点,则一定有环,由于是更新过的,则一定有负环
备份操作 防止串联
为什么最后 不是等于正无穷