- Dijkstra算法除了不适合求带负权值的,其他都可以
- 最短路径一定是简单路径
- 顶点不重复出现的是简单路径
- Floyd算法的,当最短路径修改后,pathk-1不一定是pathk的子集
- 可以判断一个有向图是否有环的:DFS,拓扑排序,求关键路径
- 拓扑排序并不要求是否连通,因此若一个有向图的顶点不能排在一个拓扑序列中,则可判定该有向图含有顶点数目大于1的强连通分量
- 一个有向图具有有序的拓扑排序序列,则它的邻接矩阵必三角
- 若没有有序,则为一般
- 如果邻接矩阵是三角,则必定有拓扑序列,即有环
- 最小生成树的边不一定比未选的边小
- DAG的拓扑序列唯一并不能唯一确定该图
- 求关键路径是以拓扑排序为基础的
- 破圈法是正确的
