文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 经管营销 > 最短路径(单源dijkstra binary_heap邻接表
侵权投诉

最短路径(单源dijkstra binary_heap邻接表

最短路径(单源dijkstra binary_heap邻接表

//单源最短路径,dijkstra算法+二分堆,邻接表形式,复杂度O(mlogm)

//求出源s到所有点的最短路经,传入图的大小n和邻接表list

//返回到各点最短距离min[]和路径pre[],pre[i]记录s到i路径上i的父结点,pre[s]=-1 //可更改路权类型,但必须非负!

#define MAXN 200

#define inf 1000000000

typedef int elem_t;

struct edge_t{

int from,to;

elem_t len;

edge_t* next;

};

#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,edge_t* list[],int s,elem_t* min,int* pre){

heap h;

edge_t* t;heap_t e;

int v[MAXN],i;

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[e.v]=1,t=list[e.v];t;t=t->next)

if (!v[t->to]&&min[t->from]+t->len<min[t->to])

第1页

你可能喜欢

热门文档

相关文档

  • 最短路径(单源dijkstra binary_heap邻接表

    最短路径(单源 dijkstra+binary_heap 邻接表.txt 我的人生有 A 面也有 B 面, 你的人生有 S 面也有 B 面。 失败不可怕, 关键看是不是成功他妈。 现在的...

  • 最短路径(单源dijkstra+binary_heap邻接表

    //单源最短路径,dijkstra算法+二分堆,邻接表形式,复杂度O(mlogm) //求出源s到所有点的最短路经,传入图的大小n和邻接表list //返回到各点最短距离min[]和...

  • 最短路径(单源dijkstra binary_heap正向表

    最短路径(单源dijkstra binary_heap正向表_互联网_IT/计算机_专业资料。急救知识_眼部烧伤急救要趁早最短路径(单源 dijkstra+binary_heap 正向表.txt 这世界上除...

  • 最短路径(单源dijkstra_bfs邻接表形式)

    最短路径(单源dijkstra_bfs邻接表形式)_法学_高等教育_教育专区。最短路径(单源dijkstra_bfs邻接表形式)//单源最短路径,用于路权相等的情况,dijkstra优化为bfs...

  • 最短路径(单源dijkstra+binary_heap正向表

    最短路径(单源dijkstra+binary_heap正向表_电脑基础知识_IT/计算机_专业资料。Acm常用函数模板,基础函数 c语言或者c++描述//单源最短路径,dijkstra算法+二分堆,...

  • 最短路径(单源dijkstra binary_heap正向表

    最短路径(单源 dijkstra+binary_heap 正向表.txt 我都舍不得欺负的人, 哪能让别人欺负? 一辈子那么长,等你几年算什么我爱的人我要亲手给她幸福 别人我不放...

  • 各种公式及模板

    最短路径(单源dijkstra+binary_heap邻接表) 113 12.5 最短路径(单源dijkstra+binary_heap正向表) 114 12.6 最短路径(单源dijkstra+mapped_heap邻接表) 115...

  • 求单源最短路径—Dijkstra算法实验报告

    求单源最短路径—Dijkstra算法实验报告_计算机软件及应用_IT/计算机_专业资料。最短路径本科学生综合性实验报告 项目组长 杨滨 成专员业_软件工程 学号_ 0123707 ...

  • 单源最短路径问题-Dijkstra

    单源最短路径问题-Dijkstra_计算机软件及应用_IT/计算机_专业资料。单源最短路径...{ -1 , -1 , -1 , -1 , 0 } }; //邻接矩阵 void main() {int ...

  • 单源最短路径算法(Dijkstra算法)

    单源最短路径算法(Dijkstra算法)_IT/计算机_专业资料。关于程序设图G=(V,E)是一个有向图,它的每一条边(U,V)都有一个非负权 W(U,V), G 中指定一个...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email