数据结构笔记(图->最短路径问题)

最短路径(Shortest Path):
网络中,两个不同顶点之间的所有路径中,边的权值之和最小的那条路径
源点(Source):
第一个顶点
终点(Destination):
最后一个顶点

单源最短路径问题:
从某个固定源点出发,求其到所有其他顶点的最短路径
1、无权图
按照递增(非递减)的顺序,找出到各个顶点的最短路径

多源最短路径问题:
求任意两顶点间的最短路径

有权图的单源最短路算法:
Dijkstra算法:参考这篇博客,讲的非常详细生动
Floyd算法:

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。