最短路径(单源dijkstra+binary_heap正向表形式)代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】最短路径(单源dijkstra+binary_heap正向表形式)

作者:imcto / 发布于2016/3/15/ 185

//单源最短路径,dijkstra算法+二分堆,正向表形式,复杂度O(mlogm)
//求出源s到所有点的最短路经,传入图的大小n和正向表list,buf
//返回到各点最短距离min[]和路径pre[],pre[i]记录s到i路径上i的父结点,pre[s]=-1
//可更改路权类型,但必须非负!
#define MAXN 200
#define inf 1000000000
typedef int elem_t;
struct edge_t{
	int to;
	elem_t len;
};

#define _cp(a,b) ((a).d<(b).d)
struct heap_t{elem_t d;int v;};
struct heap{
	heap_t h[MAXN*MAXN];
	int n,p,c;
	void init(){n=0;}
	void ins(heap_t e){
		for (p=++n;p>1&&_cp(e,h[p>>1]);h[p]=h[p>>1],p>>=1);
		h[p]=e;
	}
	int del(heap_t& e){
		if (!n) return 0;
		for (e=h[p=1],c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[p]=h[c],p=c,c<<=1);
		h[p]=h[n--];return 1;
	}
};

void dijkstra(int n,int* list,edge_t* buf,int s,elem_t* min,int* pre){
	heap h;heap_t e;
	int v[MAXN],i,t,f;
	for (i=0;i<n;i++)
		min[i]=inf,v[i]=0,pre[i]=-1;
	h.init();min[e.v=s]=e.d=0,h.ins(e);
	while (h.del(e))
		if (!v[e.v])
			for (v[f=e.v]=1,t=list[f];t<list[f+1];t++)
				if (!v[buf[t].to]&&min[f]+buf[t].len<min[buf[t].to])
					pre[buf[t].to]=f,min[e.v=buf[t].to]=e.d=min[f]+buf[t].len,h.ins(e);
}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　最短路径　

同语言下

可能有用的

imcto贡献的其它代码(12)