Tag Archives: 最短路径

数据结构重读 – 所有点对最短路径(Floyd算法)

如果我们要求每一顶点对之间的最短路径,怎么做呢?

方法1:对N个顶点,依次执行前面的Prim算法。

方法2:使用Floyd算法。

实际上,Floyd算法是动态规划(DP)算法。

原理很简单,我们假设dp[i][j]表示从顶点i到顶点j的最短路径,则dp[i][j] = min (dp[i][k]+dp[k][j], 0<=k<=nvexs)。

于是算法如下:

关于图的读取和创建,我们借[……]

继续阅读

数据结构重读 – 单源最短路径(Dijkstra)

单源最短路径:给定带权有向图和源点v,求从v到G中其余各点的最短路径。

Dijkstra算法非常类似于最小生成树算法(的Prim)。

算法

0、假设源为v0,设置辅助变量dist和pre,优先队列pq,按照dist[x]从小到达排序(小顶堆)。

1、如果v0->i连通,初始化dist[i]为w[v0][i]。放(dist[i], i)入pq。

2、循环,直到pq为空。

2.1、取出pq中最小的,设其下标为x,

2.2、遍历图matrix[x][i[……]

继续阅读