算法导论 24.3 Dijkstra算法
一，Dijkstra算法的思想
Dijkstra算法解决的是权重非负的有向图的单源最短路径问题，仍然使用的是贪心策略，每次将权值最小的结点加入集合中。
二，Dijkstra算法介绍
准备阶段：一副赋值有向图，我们定义一个集合S，表示源结点s到集合S中的结点的最短路径已经被找到，再定义一个队列Q=V-S用于存放未找到最短路径的结点。
算法过程：算法不断的从Q中选择最短路径估计值（u.d）最小的结点u加入集合S中，然后对从u发出的边进行松弛。
三，Dijkstra算法伪代码
DIJKSTRA(G,w,s)
1. INITIALIZE_SINGLE_SOURCE(G,s)
2. S=∅
3. Q=G.V
4. while Q≠∅
5. u=EXTRACT_MIN(Q)
6. S=S∪{u}
7. for each vertex v∈G.Adj[u]
8. RELAX(u,v,w)
第1-3行，对各结点进行初始化后，定义了集合S和Q，并让Q初始化为所有结点的集合；第4-8行，如果队列里还有结点未被取出，则通过EXTRACT_MIN方法取出队列Q中d值最小的结点u加入集合S中，然后对u发出的各条边进行松弛
以书上的例子为例，图a中，各个结点进行了初始化；图b中，从队列Q中选出d值最小的结点也就是源结点s，将s加入集合S并对他的两条邻边进行松弛，即他的邻结点t和y被更新为（10，s）和（5，s）；图c中，d值最小的是y，同理对x、t、z进行更新（14，y），（8，y），（7，y）；图d中，d值最小的是z，同理对x进行更新（13，z）；图e中，d值最小为t，对x进行更新（9，t）；图f中，Q中只剩余x了，他的邻结点只有z且不需要更新，至此所有结点都被加入S中
四，Dijkstra算法的复杂度
时间复杂度：O((V+E)lgV)
五，Dijkstra算法的代码
void DijkstraAlgo(Graph * graph, Node * startNode)//Dijkstra解决有向图单源最短路径，权重必须非负
{
INITIALIZE_SINGLE_SOURCE(graph, startNode); //初始化结点的d和π
vector<Node *> S;//定义一个集合S存放已经被找到最短路径的结点
vector<Node *> Q = graph->getNodeList();//定义一个集合Q存放还未被找到最短路径的结点，初始化为所有结点
while (Q.empty() != true)//直到所有边都被找到最短路径（加入到集合S中）
{
Node *u = EXTRACT_MIN(Q,startNode);//从Q中选出结点d值最小的（最靠近源节点的，第一次取出的是源节点）
S.push_back(u);//将u加入到S中
for (int i = 0; i < u->getAdjNodeList().size(); i++)//对u发出的边进行松弛
{
Node *v = u->getAdjNodeList()[i];
RELAX(u, v, graph->getEdgeList());
}
}
}