Single Source Shortest Path - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki
加权图Weighted Graph
| 边权Edge Weight | |
|---|---|
| 一般定义 | 边上的权值，代表两个结点的距离（不同场景有不同的意思） |
| 表示方法 | w(e) |
| 图例 | |
| 邻接表 | 链表上的结点也要储存边权的值 |
| 邻接矩阵 | 矩阵中aij上不再是0或1，而是边权的值 |
算法比较
| 贝尔曼-福特Bellman-Ford | 狄克斯特拉Dijkstra's | 弗洛伊德Floyd Warshall | |
|---|---|---|---|
| 时间复杂度E条边，V个结点 | O(EV) | ||
| 使用条件 | 无限制 | 所有的边权 >= 0 | |
| 数据结构 | 无，三层for循环 | 优先队列或AVL树 |