图论——最短路Dijkstra算法

Dijkstra算法：给定一个源点，求解从源点到每个点的最短路径长度。单源最短路径算法。
适用范围：有向图、边的权值没有负数

普通堆实现的Dijkstra算法最普遍、最常用：

a.节点弹出过就忽略
b.节点没弹出过，让其它没弹出节点距离变小的记录加入堆

普通堆实现的Dijkstra算法，时间复杂度o(m*1ogm)，m为边数
1，distance[i]表示从源点到i点的最短距离，visited[i]表示i节点是否从小根堆弹出过
2，准备好小根堆，小根堆存放记录：（x点，源点到x的距离），小根堆根据距离组织
3，令distance[源点]=0，（源点，0)进入小根堆
4，从小根堆弹出（u点，源点到u的距离）
a.如果visited[u]=true，不做任何处理，重复步骤4
b.如果visited[u]=false，令visited[u]=true，u就算弹出过了
然后考察u的每一条边，假设某边去往v，边权为w
1) 如果visited[v]== false并且distance[u]+ w <distance[v]
令distance[v]= distance[u] + w，把(v，distance[u]+ w)加入小根堆
2）处理完u的每一条边之后，重复步骤4
5，小根堆为空过程结束，distance表记录了源点到每个节点的最短距离。