最短路有关问题
以hdu1874为例 - 编程当前位置:& &&&最短路有关问题
以hdu1874为例最短路有关问题
以hdu1874为例&&网友分享于：&&浏览：39次最短路问题
以hdu1874为例题目链接：点击打开链接
hdu 1874比较基础，拿来练各种刚学会的算法比较好，可以避免好多陷阱，典型的最短路模板题
第一种解法：Floyd算法
&算法实现：
使用一个邻接矩阵存储边权值，两两之间能访问的必为一个有限的数，不能访问则为无穷大（用2^29代替）。注意自身和自身距离为0。
对于一对顶点 u 和 v，看看是否存在一个断点 w 使得从 u 经过 w 到 v 比已知的路径更短（包含原始输入中从 u 直接到 v 的路程）。
对所有顶点进行如上松弛操作，得到的结果是两点之间的最短路程，也可判断两点是否连通。
算法缺点：
普通的Floyd算法时间复杂度为O(n^3)，对于数据较多的情况容易TLE。但解决本题 HDU 1874 完全足够。
#include&stdio.h&
#define Max 0xfffffff
int n,m,map[201][201];
int min(int x,int y)
return x&y?y:x;
void getmap()
int a,b,i,j,l;
for(i=0;i&n;i++)
for(j=0;j&n;j++)
map[i][j]=(i==j?0:Max);
for(i=0;i&m;i++)
scanf(&%d%d%d&,&a,&b,&l);
map[a][b]=map[b][a]=min(map[a][b],l);
void floyd(int s,int e)
int i,j,k;
for(k=0;k&n;k++)
for(i=0;i&n;i++)
for(j=0;j&n;j++)
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
printf(&%d\n&,map[s][e]&Max?map[s][e]:-1);
int main()
while(scanf(&%d%d&,&n,&m)!=EOF)
scanf(&%d%d&,&s,&e);
floyd(s,e);
第二种解法：Dijkstra算法
这个算法比较经典，一般的最短路径都可以用这个来解决，耗时也比较少，不过不能处理负权路径
按路径长度递增次序产生最短路径算法：
　　把V分成两组：
　　（1）S：已求出最短路径的顶点的集合
　　（2）V-S=T：尚未确定最短路径的顶点集合
　　将T中顶点按最短路径递增的次序加入到S中，
　　保证：（1）从源点V0到S中各顶点的最短路径长度都不大于
　　从V0到T中任何顶点的最短路径长度
　　（2）每个顶点对应一个距离值
　　S中顶点：从V0到此顶点的最短路径长度
　　T中顶点：从V0到此顶点的只包括S中顶点作中间
　　顶点的最短路径长度
　　依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的
　　直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和
　　（反证法可证）
　　求最短路径步骤
　　算法步骤如下：
　　1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值
　　若存在&V0,Vi&，d(V0,Vi)为&V0,Vi&弧上的权值
　　若不存在&V0,Vi&，d(V0,Vi)为∝
　　2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
　　3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的
　　距离值比不加W的路径要短，则修改此距离值
　　重复上述步骤2、3，直到S中包含所有顶点，即S=T为止
#include&stdio.h&
#include&string.h&
#define INF 999999
int map[201][201],mark[201];
int n,m,s,e,f[201];
void dijkstra()
int i,j,k,
memset(mark,0,sizeof(mark));
for(i=0;i&n;i++)
f[i]=map[s][i];
for(i=0;i&n;i++)
for(j=0;j&n;j++)
if(!mark[j]&&min&f[j])
if(min==INF)
mark[k]=1;
for(j=0;j&n;j++)
if(!mark[j]&&f[j]&f[k]+map[k][j])
f[j]=map[k][j]+f[k];
if(f[e]!=INF) printf(&%d\n&,f[e]);
else printf(&-1\n&);
int main()
int a,b,l,i,j;
while(scanf(&%d%d&,&n,&m)!=EOF)
for(i=0;i&n;i++)
for(j=0;j&n;j++)
map[i][j]=INF;
for(i=0;i&m;i++)
scanf(&%d%d%d&,&a,&b,&l);
if(map[a][b]&l)
map[a][b]=map[b][a]=l;
scanf(&%d%d&,&s,&e);
dijkstra();
第三种解法：Bellman_Ford算法
这个算法也比较好理解，就是不断松弛操作，处理含有负权的路径
对有向图G(V,E)，用贝尔曼-福特算法求以Vs为源点的最短路径的过程：
建立dist[]、Pred[],且dist[s] = 0,其余赋无穷。Pred[]表示某节点路径上的父节点
对（Vi，Vj）属于E，比较dist[Vi] + (Vi,Vj)和dist[Vj],并将小的赋给dist[Vj]，如果修改了dist[V_j]则pred[Vj] = Vi（松弛操作）
重复以上操作V ? 1次
再重复操作一次，如dist[Vj] & dist[Vi] + (Vi,Vj),则此图存在负权环。
#include&stdio.h&
#define MAX
int m,n,d[208],start,
struct project{
int x,y,w;
}map[2008];
void Bellman_Ford()
for(i=0;i&n;i++)//Init
d[start]=0;
for(i=0;i&n;i++)
for(j=0;j&2*m;j++)
if(d[map[j].x]&d[map[j].y]+map[j].w)//relax x --w--& y
d[map[j].x]=d[map[j].y]+map[j].w;
if(d[tar]&MAX)
printf(&%d\n&,d[tar]);
else printf(&-1\n&);
int main()
while(scanf(&%d%d&,&n,&m)!=EOF)
for(i=0;i&m;i++)
scanf(&%d%d%d&,&map[i].x,&map[i].y,&map[i].w);//two way road ---&
one way road
map[i+m].y=map[i].x;
map[i+m].x=map[i].y;
map[i+m].w=map[i].w;
scanf(&%d%d&,&start,&tar);
Bellman_Ford();
第四种解法：SPFA算法
这种算法可以说是Bellman_Ford算法的优化，就是在Bellman_Ford算法的基础上加上队列实现，
SPFA(Shortest Path Faster Algorithm)
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单：
设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞，只有Dist[S]=0，Fa全部为0。
维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。
每次迭代，取出队头的点v，依次枚举从v出发的边v-&u，设边的长度为len，判断Dist[v]+len是否小于Dist[u]，若小于则改进Dist[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。若一个点入队次数超过n，则有负权环。
SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右。
SPFA算法（Shortest Path Faster Algorithm），也是求解单源最短路径问题的一种算法，用来解决：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。 SPFA算法是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算，他的基本算法和Bellman-Ford一样，并且用如下的方法改进： 1、第二步，不是枚举所有节点，而是通过队列来进行优化 设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
2、同时除了通过判断队列是否为空来结束循环，还可以通过下面的方法： 判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。
SPFA算法有两个优化算法 SLF 和 LLL&
SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)&dist(i)，则将j插入队首，否则插入队尾。 LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)&x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)&=x，则将i出对进行松弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。
#include&stdio.h&//SPFA 模拟队列实现最短路径
#include&string.h&
#define INF 100000
int map[210][210],flag[210],Q[210],d[210];
int m,n,start,
void SPFA()
int front=0,rear=0;
memset(Q,0,sizeof(Q));
memset(flag,0,sizeof(flag));
for(i=0;i&n;i++)
d[start]=0;
flag[start]=1;
while(front&rear)
x=Q[front];//出队列
front=(front+1)%210;
flag[x]=0;
for(i=0;i&n;i++)
if(d[i]&d[x]+map[x][i])
d[i]=d[x]+map[x][i];
if(!flag[i])
Q[rear]=i;//入队列
rear=(rear+1)%210;
flag[i]=1;
if(d[tar]&INF)
printf(&%d\n&,d[tar]);
else printf(&-1\n&);
int main()
int i,j,a,b,c;
while(scanf(&%d%d&,&n,&m)!=EOF)
for(i=0;i&n;i++)
for(j=0;j&n;j++)
map[i][j]=INF;
for(i=0;i&m;i++)
scanf(&%d%d%d&,&a,&b,&c);
if(map[a][b]&c)
map[a][b]=map[b][a]=c;
scanf(&%d%d&,&start,&tar);
其实最短路总结就一句话，不断的进行松弛操作，无论是什么解法，都要进行松弛操作，然后找到最短路径
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有带点弧约束的最短路问题——复杂性和算法--《应用数学》1999年03期
带点弧约束的最短路问题——复杂性和算法
【摘要】：本文首先提出了带点弧约束的最短路问题，证明了该问题属于ＮＰ－Ｃ，然后给出了一个伪多项式时间算法．最后给出了最小成本最短路问题的一个时间复杂性为Ｏ（ｎ２）的算法．
【作者单位】：
【关键词】：
【分类号】：O224【正文快照】：
最短路问题是网络优化中一个经典问题，其变形问题——带弧成本约束的最短路问题，引起了许多研究工作者和实际工作者的兴趣，具有广泛的实际背景．定义１Ｇ＝〈Ｎ，Ａ，Ｌ〉是一个网络，｜Ｎ｜＝ｎ，｜Ａ｜＝ｍ．?〈ｖｉ，ｖｊ〉∈Ａ，有非负参数ｌｉｊ，称作长度；有非负
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【共引文献】
中国期刊全文数据库
陈荣军;[J];常州工学院学报;1999年02期
顾朝林;[J];地理学报;1991年02期
高随祥,高丽丽;[J];系统工程;1994年04期
李帮义,姚恩瑜;[J];系统工程;1999年05期
秦昆,关泽群,李德仁,周军其;[J];国土资源遥感;2002年02期
陆宁,马振东;[J];基建优化;1989年05期
宿洁,袁军鹏;[J];计算机工程与应用;2003年30期
赵太飞;李乐民;虞红芳;;[J];计算机应用研究;2007年11期
王德明，王省身，崔岗;[J];煤炭学报;1994年01期
王世定;杨培君;;[J];水电能源科学;1991年03期
中国博士学位论文全文数据库
冯小平;[D];同济大学;2007年
赵太飞;[D];电子科技大学;2007年
张可;[D];北京工业大学;2001年
孙宏;[D];西南交通大学;2003年
张庆年;[D];武汉理工大学;2003年
刘广义;[D];清华大学;2004年
杨传勇;[D];武汉大学;2005年
李圣权;[D];武汉大学;2004年
谭涛;[D];大连理工大学;2006年
中国硕士学位论文全文数据库
王洪顺;[D];新疆农业大学;2003年
邵玉华;[D];西南交通大学;2003年
李书;[D];西南交通大学;2003年
孙续;[D];西北工业大学;2004年
黄彦浩;[D];武汉大学;2004年
李旭华;[D];中北大学;2005年
刘治平;[D];山东大学;2005年
秦挺峰;[D];江南大学;2004年
王洋;[D];北京工业大学;2007年
郝晓军;[D];河北工业大学;2003年
【相似文献】
中国期刊全文数据库
秦裕瑗;[J];数学杂志;1981年02期
秦裕瑗;;[J];武汉科技大学学报(自然科学版);1981年02期
马仲蕃;;[J];运筹学学报;1982年01期
方伟武;[J];应用数学学报;1983年03期
雷文安;[J];四川师范大学学报(自然科学版);1984年04期
董纯飞;刘为国;;[J];运筹学学报;1984年01期
卢学妙;;[J];云南师范大学学报(自然科学版);1985年01期
朱廷昌,王志学;[J];长春工业大学学报(自然科学版);1986年02期
,陈蕴衡;[J];太原重型机械学院学报;1986年02期
马川生;[J];系统工程;1986年04期
中国重要会议论文全文数据库
严余松;;[A];管理科学与系统科学进展——全国青年管理科学与系统科学论文集（第4卷）[C];1997年
潘腾;晏磊;邓中亮;;[A];全国第16届计算机科学与技术应用（CACIS）学术会议论文集[C];2004年
李引珍;何瑞春;郭耀煌;;[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年
李引珍;何瑞春;郭耀煌;;[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年
胡劲松;吴斐;戴更新;;[A];第六届中国青年运筹与管理学者大会论文集[C];2004年
许云飞;;[A];第四届亚太可持续发展交通与环境技术大会论文集[C];2005年
夏少刚;张建华;;[A];中国运筹学会第八届学术交流会论文集[C];2006年
薛怡珍;邱祈榮;方偉達;賴明洲;李吳嘉;張小飛;;[A];第四届海峡两岸GIS发展研讨会暨中国GIS协会第十届年会论文集[C];2006年
徐卫亚;周家文;邓俊晔;石崇;张宗亮;刘兴宁;;[A];第一届中国水利水电岩土力学与工程学术讨论会论文集（上册）[C];2006年
马建生;孙玺菁;黄连杰;;[A];提高全民科学素质、建设创新型国家——2006中国科协年会论文集（下册）[C];2006年
中国重要报纸全文数据库
天津市赛恩师网络研究中心主任
王汝林;[N];中华工商时报;2001年
PALADIN;[N];电脑报;2003年
吴淑侠;[N];河北经济日报;2004年
安徽记者　 陈晶晶;[N];中国邮政报;2006年
王义安;[N];解放军报;2006年
李文奇 鲁勇;[N];联合日报;2008年
中国博士学位论文全文数据库
雷定猷;[D];中南大学;2005年
魏航;[D];西南交通大学;2006年
韩世莲;[D];东南大学;2006年
古继兴;[D];上海交通大学;2007年
计小宇;[D];清华大学;2006年
中国硕士学位论文全文数据库
张振抻;[D];郑州大学;2002年
苏健;[D];西安电子科技大学;2004年
王壮志;[D];长沙理工大学;2004年
宫乘霞;[D];山东科技大学;2005年
樊晓香;[D];安徽大学;2005年
王培宏;[D];天津大学;2005年
于洁潇;[D];天津大学;2005年
邓俊晔;[D];河海大学;2006年
罗晓玲;[D];西南交通大学;2006年
王靖;[D];电子科技大学;2006年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号Hamming距离下的最短路逆问题--《河海大学学报(自然科学版)》2008年04期
Hamming距离下的最短路逆问题
【摘要】：针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.
【作者单位】：
【关键词】：
【基金】：
【分类号】：TP301.6【正文快照】：
由于网络优化逆问题不仅有很重要的理论研究价值,而且有较大的实际应用价值,因此该问题的研究最近受到许多学者的重视.文献[1]研究了l2范数下的最短路逆问题,通过转化为二次规划问题而求解该问题.文献[2]考虑了l1范数下的最短路逆问题,应用线性规划及给出的一个列生成算法解
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【共引文献】
中国期刊全文数据库
陈志民;;[J];长春师范学院学报;2007年04期
陈荣军;;[J];常州工学院学报;2006年06期
张峰;陈德伍;唐国春;;[J];工程数学学报;2010年06期
魏航,蒲云,李军;[J];系统工程;2005年07期
郝光;张殿业;王东梅;;[J];公路交通科技;2007年11期
张斌武;王勤;;[J];兰州理工大学学报;2008年02期
张斌武;王勤;余维燕;;[J];兰州理工大学学报;2008年04期
;[J];Applied Mathematics:A Journal of Chinese U2001年02期
张斌武,何勇;[J];高校应用数学学报A辑(中文版);2004年S1期
张斌武;王勤;;[J];河海大学常州分校学报;2007年04期
中国博士学位论文全文数据库
张斌武;[D];浙江大学;2005年
马立杰;[D];山东大学;2007年
郝光;[D];西南交通大学;2007年
刘耕;[D];华中科技大学;2007年
肖现涛;[D];大连理工大学;2009年
陈伟;[D];华中科技大学;2009年
刘龙城;[D];浙江大学;2009年
姜永;[D];大连理工大学;2011年
【相似文献】
中国期刊全文数据库
赵福生;;[J];福建电脑;2011年06期
杨本胜;;[J];电脑知识与技术;2011年13期
唐长铁;;[J];山西建筑;2011年28期
李琳琳;梅生;李钊;李承剑;;[J];无线电工程;2011年07期
黄军伟;何元飞;张艳晓;董金明;;[J];中国科技信息;2011年15期
郑秀雷;李明;;[J];电脑知识与技术;2011年23期
吴洁明;李余琪;万励;;[J];微电子学与计算机;2011年07期
聂俊岚;王小彦;陈子军;刘文远;;[J];小型微型计算机系统;2011年06期
杨康;李满春;刘永学;程亮;江冲亚;;[J];遥感技术与应用;2011年03期
白艳琴;王勤;吴龙树;;[J];计算机工程与应用;2011年19期
中国重要会议论文全文数据库
吴国凤;曾标;;[A];IT服务促进企业信息化——第十一届中国Java技术及应用交流大会文集[C];2008年
胡洪林;;[A];2008年计算机应用技术交流会论文集[C];2008年
李舒蕊;禤宇明;;[A];第十二届全国心理学学术大会论文摘要集[C];2009年
黄跃峰;钟耳顺;;[A];中国测绘学会第九次全国会员代表大会暨学会成立50周年纪念大会论文集[C];2009年
林家恒;王钊;刘长有;;[A];1995中国控制与决策学术年会论文集[C];1995年
施培港;;[A];中国地理信息系统协会第三次代表大会暨第七届年会论文集[C];2003年
刘玉华;宫继红;宋文杰;宋拥军;;[A];山东省测绘学术年会论文集[C];2006年
高学辉;孙晧;;[A];第一届中国智能交通年会论文集[C];2005年
许世峰;高军;杨冬青;王腾蛟;;[A];第26届中国数据库学术会议论文集（A辑）[C];2009年
潘腾;晏磊;邓中亮;;[A];全国第16届计算机科学与技术应用（CACIS）学术会议论文集[C];2004年
中国重要报纸全文数据库
周祥;[N];中国计算机报;2003年
赵正;[N];中国经营报;2004年
沈占锋;[N];计算机世界;2007年
应凯;[N];电脑报;2005年
金桦;[N];中国计算机报;2003年
内蒙古建设银行包头分行 薛志强;[N];网络世界;2002年
本报实习记者
尹锋;[N];通信信息报;2004年
宋献涛;[N];计算机世界;2002年
郑宗杰;[N];中国交通报;2006年
李刚;[N];中华工商时报;2007年
中国博士学位论文全文数据库
何富贵;[D];安徽大学;2011年
郑虹;[D];吉林大学;2012年
桑永胜;[D];电子科技大学;2010年
于春荣;[D];吉林大学;2008年
王伟;[D];武汉大学;2004年
马明全;[D];西北大学;2007年
裴钟哲;[D];北京工业大学;2004年
罗亮;[D];华中科技大学;2010年
陈驻民;[D];东华大学;2010年
陈泳;[D];浙江大学;2004年
中国硕士学位论文全文数据库
郑小飞;[D];东华大学;2011年
戴阳;[D];第二军医大学;2005年
熊少非;[D];国防科学技术大学;2004年
柴秀荣;[D];中国科学技术大学;2009年
张永梅;[D];华北工学院;2002年
张池军;[D];吉林大学;2005年
杨汉卿;[D];西北大学;2005年
陶泽柳;[D];合肥工业大学;2005年
黄河;[D];武汉理工大学;2007年
潘庆先;[D];上海交通大学;2008年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号最短路算法详解（dijkstra/SPFA/floyd） - 推酷
最短路算法详解（dijkstra/SPFA/floyd）
一、Dijkstra
Dijkstra单源最短路算法，即计算从起点出发到每个点的最短路。所以Dijkstra常常作为其他算法的预处理。
&使用邻接矩阵的时间复杂度为O(n^2),用优先队列的复杂度为O(mlogn)
(一)& 过程
每次选择一个未访问过的到已经访问过（标记为Known）的所有点的集合的最短边，并用这个点进行更新，过程如下：
Dv为最短路，而Pv为前面的顶点。
1.&&&& 初始
2.&&&& 在v1被标记为已知后的表
3.&&&& 下一步选取v4并且标记为known，顶点v3,v5,v6,v7是邻接的顶点，而他们实际上都需要调整。如表所示:
4.&&&& 接下来选取v2,v4是邻接点，但已经是known的，不需要调整，v5是邻接的点但不做调整，因为经过v2的值为2+10=12而长为3的路径已经是已知的。
5.&&&& 接下来选取v5，值为3，v7 3+6&5不需调整，然后选取v3，对v6的距离下调到3+5=8
6.&&&& 再选下一个顶点是v7，v6变为5+1=6
7.&&&& 最后选取v6
(二)& 局限性
Dijkstra没办法解决负边权的最短路径，如图
运行完该算法后，从顶点
的最短路径为
，其长度为
，而实际上最短路径为
，其长度为
（因为过程中先选择
被标记为已知，今后不再更新）
算法实现。
．普通的邻接表&
用vis作为上面标记的known，dis记录最短距离（记得初始化为一个很大的数）。
void dijkstra(int s)
memset(vis,0,sizeof(vis));
int cur=s;
dis[cur]=0;
vis[cur]=1;
for(int i=0;i&n;i++)
for(int j=0;j&n;j++)
if(!vis[j] && dis[cur] + map[cur][j] & dis[j])
//未被标记且比已知的短，可更新
dis[j]=dis[cur] + map[cur][j] ;
int mini=INF;
for(int j=0;j&n;j++)
if(!vis[j] && dis[j] & mini)
//选择下一次到已知顶点最短的点。
mini=dis[cur=j];
2.邻接表+优先队列。
要重载个比较函数。
struct point
point(int id,int val):id(id),val(val){}
bool operator &(const point &x)const{
return val&x.
void dijkstra(int s)
memset(vis,0,sizeof(vis));
for(int i=0;i&n;i++)
dis[i]=INF;
priority_queue&point&
q.push(point(s,0));
while(!q.empty())
int cur=q.top().
for(int i=head[cur];i!=-1;i=e[i].next)
int id=e[i].
if(!vis[id] && dis[cur]+e[i].val & dis[id])
dis[id]=dis[cur]+e[i].
q.push(point(id,dis[id]));
二、SPFA（bellman-ford）
SPFA是bellman-ford的改进算法(队列实现），效率也更高，故直接介绍SPFA。
相比于Dijkstra，SPFA可以计算带负环的回路。
邻接表的复杂度为：O(kE)E为边数，k一般为2或3
（一）原理过程：
bellman-ford算法的基本思想是，对图中除了源顶点s外的任意顶点u，依次构造从s到u的最短路径长度序列dist[u],dis2[u]……dis(n-1)[u]，其中n是图G的顶点数，dis1[u]是从s到u的只经过1条边的最短路径长度，dis2[u]是从s到u的最多经过G中2条边的最短路径长度……当图G中没有从源可达的负权图时，从s到u的最短路径上最多有n-1条边。因此，
dist(n-1)[u]就是从s到u的最短路径长度，显然，若从源s到u的边长为e(s,u)，则dis1[u]=e(s,u).对于k&1，dis（k)[u]满足如下递归式，dis(k)[u]=min{dis(k-1)[v]+e(v,u)}.bellman-ford最短路径就是按照这个递归式计算最短路的。
SPFA的实现如下：用数组dis记录更新后的状态，cnt记录更新的次数，队列q记录更新过的顶点，算法依次从q中取出待更新的顶点U,按照dis(k)[u]的递归式计算。在计算过程中，一旦发现顶点K有cnt[k]&n，说明有一个从顶点K出发的负权圈，此时没有最短路，应终止算法。否则，队列为空的时候，算法得到G的各顶点的最短路径长度。
（二）实现：
1.邻接矩阵的SPFA
void SPFA(int s)
for(int i=0;i&n;i++)
dis[i]=INF;
bool vis[MAXN]={0};
queue&int&
q.push(s);
while(!q.empty())
int cur=q.front();
for(int i=0;i&n;i++)
if(dis[cur] + map[cur][i] & dis[i])
dis[i]=dis[cur] + map[cur][i];
if(!vis[i])
q.push(i);
2.邻接表的SPFA（推荐）
void spfa(int s)
memset(vis,0,sizeof(vis));
for(int i=0;i&n;i++)
dis[i]=INF;
queue&int&
q.push(s);
while(!q.empty())
int cur=q.front();
for(int i=head[cur];i!=-1;i=e[i].next)
int id=e[i].
if(dis[id] & dis[cur]+e[i].val)
dis[id] = dis[cur] + e[i].
if(!vis[id])
q.push(id);
3.上面的两个都没有对负圈的判断，因为题目的限制就是正的。判断负环代码如下：以
bool spfa()
for(int i=0;i&=n;i++)
dis[i]=INF;
bool vis[MAXN]={0};
int cnt[MAXN]={0};
queue&int&
q.push(0);
while(!q.empty())
int cur=q.front();
for(int i=head[cur];i!=-1;i=e[i].next)
int id=e[i].
if(dis[cur] + e[i].val & dis[id])
dis[id]=dis[cur]+e[i].
if(!vis[id])
cnt[id]++;
if(cnt[cur] & n)
q.push(id);
（三）：优化
SLF（Small Label First）是指在入队时如果当前点的dist值小于队首， 则插入到队首， 否则插入到队尾。
LLL不太常用，我也没研究。
（四）应用：
眼见的同学应该发现了，上面的差分约束四个字，是的SPFA可以很好的实现差分约束系统。
近几天会把差分约束也整理出来~
全称Floyd-Warshall。记得离散数学里面有Warshall算法，用来计算传递闭包。而数据结构每次都简称floyd，当时就觉得两个都差不多，有神马关系，后来google一下发现是同一个算法。。。。改个名字出来走江湖啊！！！！！
这个算法用于求所有点对的最短距离。比调用n次dijkstra的优点在于代码简单。
时间复杂度为O(n^3)
（一）原理过程：这是一个dp（动态规划的过程）
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
即从顶点i到j且经过顶点k的最短路径长度。
（二）实现：
void floyd()
for(int k=0;k&n;k++)
for(int i=0;i&n;i++)
for(int j=0;j&n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
如走迷宫经常用的BFS，以一个点出发，向外扩散。
除了上面的
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致}