两顶点之间的距离是指他们之间最短路径的长度，需要注意的是两个顶点之间可能有多条最短路径
顶点 v 的偏心率：v 和其它顶点的距离的最大值，也即是这个点和离其最远点的距离
图半径：最小的偏心率
图直径：最大的偏心率，也即最远的两点间的距离。若要求得一张图的直径，首先要求得任意两点之间的最短路径，在这些所有的最短路径中，取其长度最长者，即是这张图的直径
不考虑权重的有向图
| from_id | to_id | distance |
|---|---|---|
| 1 | 2 | 1 |
| 3 | 2 | |
| 4 | 4 | |
| 5 | 3 | |
| 6 | 4 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 3 | |
| 5 | 2 | |
| 6 | 3 | |
| 3 | 1 | |
| 2 | 3 | |
| 4 | 2 | |
| 5 | 1 | |
| 6 | 2 | |
| 4 | 1 | |
| 2 | 1 | |
| 3 | 2 | |
| 5 | 3 | |
| 6 | 4 | |
| 5 | 1 | |
| 2 | 2 | |
| 3 | 3 | |
| 4 | 1 | |
| 6 | 1 | |
| 6 | 1 | |
| 2 | ||
| 3 | ||
| 4 | ||
| 5 |
所以，
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 偏心率 | 4 | 3 | 3 | 4 | 3 |
半径为3，直径为4
加权的有向图
此时，顶点 3 到 顶点5 的 距离 为 7
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/118391.html