数据结构重读 – 单源最短路径(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], i 0->nvexs。如果dist[x]+matrix[x][i] < dist[i],更新dist[i]=dist[x]+matrix[x][i],并且放(dist[i], i)入pq,并且pre[i] = x。

3、如果dist[i]<INFINTE,输出dist[i],并倒序输出pre[?]直到为-1。

上述这么搞,时间复杂度应该为O(nlogn)

好了,代码如下:

图及输入

Dijkstra算法

测试图:

测试数据:

测试输出:

 

 

 

Leave a Reply

Your email address will not be published.