这是一个简易的Dijkstra算法的优化实现，利用了堆，这里使用C++中的优先级队列。利用STL内置的堆实现只是优化的第一步，更进一步的优化包括使用Fibonacci堆等更高级数据结构。

算法中，使用邻接表作为存储图的数据结构，利用一个int数组d保存过程中及最后得到的最短路长度，再自定义一个pair<int, int>来保存在堆中的当前最短路，pair的first元素用来保存路径长度，second元素保存所对应的节点数。堆以first的值作为比较元素，通过second值得到其节点索引，再到邻接表中查找出边，将所有出边relax掉（也就是更新d中的最短距离）。直到队列为空，停止算法。

这个Dijkstra算法不是那么容易说清楚的。在众多算法中，个人感觉这个算法在实现上逻辑比较复杂（关乎实现）。算法本身很直观，但因为涉及到图，其各种操作都要退化到程序中迭代实现，比起堆排序、快排、KMP等算法，需要一些新的编程技巧和思维习惯。

Talk is cheap, show you the code.

 

struct Edge{ int to, cost; };typedef pair
     
       P;const int M = 10;const int V = 10;const int INF = 1 << 30;vector
      
        E[M];int d[V];void dij(int s,int t){	fill(d, d + V, INF);	d[s] = 0;	priority_queue
       
        
, greater
        
 > q;	q.push(P(0, s));	while(!q.empty()){		P p = q.top();		q.pop();		int to = p.second;		int cost = p.first;		for (int i = 0; i < E[to].size(); i++)		{			Edge e = E[to][i];			if (d[e.to]>d[to] + e.cost)			{				d[e.to] = d[to] + e.cost;				q.push(P(d[e.to], e.to));			}		}	}}