My Little World

最短路径

网图:两个顶点经过的边上权值之和最少的路径
非网图:两个顶点之间经过的边数最少的路径
源点:路径起始的第一个顶点
终点:最后一个顶点
shortestpath1

迪杰斯特拉(Dijkstra)算法

一个顶点到所有顶点的最短路径
主要思路:一步步求出它们之间顶点的最短路径,过程中都是基于已经求出的最短路径的基础上,求得更远顶点的最短路径
编程思路:类似于最小生成树普里姆算法
代码链接

佛洛依德(Floyd)算法

扩展版迪杰斯特拉(Dijkstra)算法,求图中所有结点到所有结点的最大路径,结果由二维数组展现
代码链接
shortestpath2