Dijkstra算法简述
Dijkstra算法是图论中的一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：集合T包含所有当前已经找到最短路径的点，初始情况下T中只有源点。U维护当前源点通过T中各点到达其他各点的距离。从源点开始，每次新扩展一个属于U、距离T中点最短的点，用该点更新U中的与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。
Dijkstra算法流程
在以下说明中，start为源，Adj[u,v]为点u和v之间的边的长度，结果保存在Closest[]
- 初始化：源的距离Closest[start]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。
- 以下过程循环n-1次：
在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
对于每个与u相邻的点v，如果Closest[u]+Adj[u,v] < Closest[v]，那么把Closest[v]更新成更短的距离Closest[u]+Adj[u,v]。此时到点v的最短路径上，前一个节点即为u。
- 结束。此时对于任意的u，Closest[u]就是start到u的距离。
//呵呵，有点简陋，但是思想还是正确地
#include <iostream>
using namespace std;
const int max_vertexes = 3;
const int infinity = 10001;
int graph[max_vertexes][max_vertexes]={
0,1,5,
infinity,0,2,
infinity,infinity,infinity
};
//typedef **int Graph;
int path[max_vertexes];
int n,s,t;
int Dijkstra(int G[max_vertexes][max_vertexes],int n,int s,int t, int path[])
{
int i,j,w,minc,d[max_vertexes],flag[max_vertexes];
memset(flag,0,sizeof(flag));
for (i=0;i<n;i++)
{
d[i]=G[s][i];
path[i]=s;//都从S直接到达的
}
flag[s]=1;
path[s]=0;//s点为第一步
d[s]=0;
for (i=1;i<n;i++)
{
minc=infinity;
w=0;
for(j=0;j<n;j++)//找出一个到S距离最短的未添加的节点
if ((flag[j]==0)&&(minc>=d[j]))
{
minc=d[j];
w=j;
}
flag[w]=1;
for (j=0;j<n;j++)//更新路径
if((flag[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j]))
{
d[j]=d[w]+G[w][j];
path[j]=w;
}
}
return d[t];
}
int main(void)
{
int s,t;
while(cin>>s>>t)
{
int result = Dijkstra(graph,max_vertexes,s,t,path);
cout<<result<<endl;
}
return 0;
}
堆优化版：
描述:
回忆经典dijkstra算法
每次在没标记的节点中找离源点最近的,此步骤可以用HEAP维护,每次取根(最小值),然后删除根,在其左右儿子中选更小的作为堆的根,但此时选中的子树有无根了,递归处理.
找到最近点后,要更新各点离源点的距离,若能更新,则该点的值变小了,可能比其父亲更小,与其比较,更小就交换,不断往上比较,直到是整个堆的根或不比父亲小.
heap里存顶点（按dist的顺序）
repeat
relax从heap[1]发出的每一条边，当然，一边relax一边fixup，
delete(heap[1])，fixdown
until empty(heap);
复杂度分析:
众所周知没有经过优化的dijkstra算法的复杂度为O(V^2)
算法使用了堆，每次以最小代价加入顶点，即deletemin操作(O(logn))
然后根据该点调整其他顶点到当前树的距离，主要用到decreasekey操作(logn)
因为decrease最多m次，所以decrease花掉 O(mlogn)的时间，deletemin执行n次，它花掉O(nlogn)时间，一共O((m+n)logn)时间。而其初始化部分的复杂度不超过这个值，所以算法总复杂度O((m+n)logn)(当然这个复杂度只适用于邻接表表示的稀疏图)
#include <iostream>
#include <vector>
using namespace std;
const unsigned int NoEdge=0xfffffff;
struct vertex{
int n;
int weight;
};
vertex heap[100];
int ph[100];//ph[i]存放顶点i在堆中的下标,当i的位置改变时它也随之改变
int size;//堆的大小
inline int parent(int i)
{
return (i+1)/2-1;
}
inline int left(int i)
{
return (i+1)*2-1;
}
inline int right(int i)
{
return (i+1)*2;
}
void heapify(int i)
{
int smallest=i;
if(left(i)<size&&heap[left(i)].weight<heap[smallest].weight)
{
smallest=left(i);
}
if(right(i)<size&&heap[right(i)].weight<heap[smallest].weight)
{
smallest=right(i);
}
if(smallest!=i)
{//交换heap[smallest]和heap[i]中的值,并实ph[]中的值与交换后的情况一致
ph[heap[smallest].n]=i;
ph[heap[i].n]=smallest;
vertex temp;
temp=heap[smallest];
heap[smallest]=heap[i];
heap[i]=temp;
heapify(smallest);
}
}
vertex extract()
{
//得到从原点出发的可到达的最近的点
vertex min=heap[0];
heap[0]=heap[--size];
ph[heap[0].n]=0;
heapify(0);
return min;
}
void build()
{
//initialize a heap from an array , but not used in Dijkstra.
for(int i = parent(size-1) ; i >=0 ; --i)
{
heapify(i);
}
}
void decrease(int i,int key)
{
//更新heap[i]的值为key,且key必须为非负
heap[i].weight=key;
while(i>0&&heap[i].weight<heap[parent(i)].weight)
{
ph[heap[i].n]=parent(i);
ph[heap[parent(i)].n]=i;
vertex temp;
temp=heap[i];
heap[i]=heap[parent(i)];
heap[parent(i)]=temp;
i=parent(i);
}
}
bool empty()
{//测试堆是否为空
return size==0;
}
int n;//顶点的个数
int d[100];//存放从原点到此顶点的最短距离
vector<vertex> v[100];
void Dijkstra(int source)
{
for(int i = 0 ; i < n ; ++i )
{
heap[i].n=i;
heap[i].weight=NoEdge;
ph[i]=i;
}
decrease(source,0);
vertex min;
while(!empty())
{
min=extract();
d[min.n]=min.weight;
cout << endl;
for(vector<vertex>::iterator itr=v[min.n].begin();itr!=v[min.n].end();++itr)
{
if(heap[ph[itr->n]].weight>min.weight+itr->weight)
{
decrease(ph[itr->n],min.weight+itr->weight);
}
}
}
}
int main()
{
int a,b,w;
int edges;
vertex temp;
cin >> n;
cin >> edges;
size=n;
for(int i = 0 ; i < n ; ++i )
{
d[i]=NoEdge;
}
for(int i = 0 ; i < edges; ++i )
{
cin >> a >> b >> w;
temp.n=b;
temp.weight=w;
v[a].push_back(temp);
}
int s,t;
while(cin>>s>>t)
{
Dijkstra(s);
cout<<d[t]<<endl;
}
return 0;
}