数据结构和算法
有向带权图的最算路径问题
有向带权图的单源最短路径问题：迪杰斯特拉算法
有向带权图的多源最短路径问题：佛洛依德算法
单源最短路径问题
概念
如果从A节点出发的话，计算出从A节点到达其他节点的最短路径，这就是单源最短路径问题。
迪杰斯特拉算法
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | 0 | 24 | 8 | 15 | ∞ | ∞ | ∞ |
| B | ∞ | 0 | ∞ | ∞ | 6 | ∞ | ∞ |
| C | ∞ | ∞ | 0 | ∞ | 7 | 3 | ∞ |
| D | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 4 |
| E | ∞ | ∞ | ∞ | ∞ | 0 | ∞ | 9 |
| F | ∞ | ∞ | ∞ | 5 | 2 | 0 | 10 |
| G | ∞ | 3 | ∞ | ∞ | ∞ | ∞ | 0 |
在有向图中，从节点m到节点n之间具有边相连，但是并不代表从节点n出发返回节点m同样具有相连的边，既是具有相连的边，边的权值也有可能不同，所以，有向图的邻接矩阵表是一个不对称的矩阵
| A | B | C | D | E | F | G | 从A点能抵达的点的集合 | |
|---|---|---|---|---|---|---|---|---|
| 最短距离 | 24 | 8 | 15 | |||||
| 最短路径 | AB |
最短距离：即从A点出发，直接连通或者经过其他节点到达这一节点的边权之和；
最短路径：记录一个字符串，用来表示从A点出发，直接连通或者经过其他节点到达这一节点的路径，字符串结尾一定是这个节点的取值。例如：B列最终的最短路径是ADGB，表示从A节点出发，途经D节点和G节点最终达到B节点，就是从A节点到B节点的最短路径；