posts - 195, comments - 34, trackbacks - 0, articles - 1
阅读排行榜
评论排行榜
最短路径&之&SPFA算法&(转载）
求最短路径的算法有许多种，除了排序外，恐怕是OI界中解决同一类问题算法最多的了。最熟悉的无疑是Dijkstra，接着是Bellman-Ford，它们都可以求出由一个源点向其他各点的最短路径；如果我们想要求出每一对顶点之间的最短路径的话，还可以用Floyd-Warshall。
SPFA是这篇日志要写的一种算法，它的性能非常好，代码实现也并不复杂。特别是当图的规模大，用邻接矩阵存不下的时候，用SPFA则可以很方便地面对临接表。每个人都写过广搜，SPFA的实现和广搜非常相似。
如何求得最短路径的长度值？
首先说明，SPFA是一种单源最短路径算法，所以以下所说的“某点的最短路径长度”，指的是“某点到源点的最短路径长度”。
我们记源点为S，由源点到达点i的“当前最短路径”为D[i]，开始时将所有D[i]初始化为无穷大，D[S]则初始化为0。算法所要做的，就是在运行过程中，不断尝试减小D[]数组的元素，最终将其中每一个元素减小到实际的最短路径。
过程中，我们要维护一个队列，开始时将源点置于队首，然后反复进行这样的操作，直到队列为空：
(1)从队首取出一个结点u，扫描所有由u结点可以一步到达的结点，具体的扫描过程，随存储方式的不同而不同；
(2)一旦发现有这样一个结点，记为v，满足D[v] & D[u] + w(u, v)，则将D[v]的值减小，减小到和D[u] + w(u, v)相等。其中，w(u, v)为图中的边u-v的长度，由于u-v必相邻，所以这个长度一定已知（不然我们得到的也不叫一个完整的图）；这种操作叫做松弛。
松弛操作的原理是著名的定理：“三角形两边之和大于第三边”，在信息学中我们叫它三角不等式。所谓对i,j进行松弛，就是判定是否d[j]&d[i]+w[i,j]，如果该式成立则将d[j]减小到d[i]+w[i,j]，否则不动。
(3)上一步中，我们认为我们“改进了”结点v的最短路径，结点v的当前路径长度D[v]相比于以前减小了一些，于是，与v相连的一些结点的路径长度可能会相应地减小。注意，是可能，而不是一定。但即使如此，我们仍然要将v加入到队列中等待处理，以保证这些结点的路径值在算法结束时被降至最优。当然，如果连接至v的边较多，算法运行中，结点v的路径长度可能会多次被改进，如果我们因此而将v加入队列多次，后续的工作无疑是冗余的。这样，就需要我们维护一个bool数组Inqueue[]，来记录每一个结点是否已经在队列中。我们仅将尚未加入队列的点加入队列。
算法能否结束？
对于不存在负权回路的图来说，上述算法是一定会结束的。因为算法在反复优化各个最短路径长度，总有一个时刻会进入“无法再优化”的局面，此时一旦队列读空，算法就结束了。然而，如果图中存在一条权值为负的回路，就糟糕了，算法会在其上反复运行，通过“绕圈”来无休止地试图减小某些相关点的最短路径值。假如我们不能保证图中没有负权回路，一种“结束条件”是必要的。这种结束条件是什么呢？
思考Bellman-Ford算法，它是如何结束的？显然，最朴素的Bellman-Ford算法不管循环过程中发生了什么，一概要循环|V|-1遍才肯结束。凭直觉我们可以感到，SPFA算法“更聪明一些”，就是说我们可以猜测，假如在SPFA中，一个点进入队列——或者说一个点被处理——超过了|V|次，那么就可以断定图中存在负权回路了。
最短路径本身怎么输出？
在一幅图中，我们仅仅知道结点A到结点E的最短路径长度是73，有时候意义不大。这附图如果是地图的模型的话，在算出最短路径长度后，我们总要说明“怎么走”才算真正解决了问题。如何在计算过程中记录下来最短路径是怎么走的，并在最后将它输出呢？
Path[]数组，Path[i]表示从S到i的最短路径中，结点i之前的结点的编号。注意，是“之前”，不是“之后”。最短路径算法的核心思想成为“松弛”，原理是三角形不等式，方法是上文已经提及的。我们只需要在借助结点u对结点v进行松弛的同时，标记下Path[v] = u，记录的工作就完成了。
输出时可能会遇到一点难处，我们记的是每个点“前面的”点是什么，输出却要从最前面往最后面输，这不好办。其实很好办，见如下递归方法：
void PrintPath(int k){
&&&&if( Path[k] ) PrintPath(Path[k]);
&&&&fout&&k&&' ';
SPFA的代码怎么写？
我写了邻接表和邻接矩阵两种，两者想像起来是那么的不同，算法的思路上实在区别不大，只是用不同方式诠释“扫描”的过程而已。只给出SPFA的单个函数，我不觉得很容易看懂，但是我仍然把两个程序的SPFA函数放在下面。在日志的结尾处，有一个完整版文件下载。贴程序，首先是邻接表的：
void SPFA(){
&&&&for(int i=1; i&= i++)
&&&&&&&&Dist[i] = 100000;
&&&&Dist[S] = 0;
&&&&int closed = 0, open = 1;
&&&&queue[1] = S;
&&&&Inqueue[S] =
&&&&&&&&closed++;
&&&&&&&&node *tmp = connect[queue[closed]];
&&&&&&&&Inqueue[queue[closed]] =
&&&&&&&&while(tmp != NULL){
&&&&&&&&&&&&if( Dist[tmp-&key] & Dist[queue[closed]] + tmp-&w ){
&&&&&&&&&&&&&&&&Dist[tmp-&key] = Dist[queue[closed]] + tmp-&w;
&&&&&&&&&&&&&&&&Path[tmp-&key] = queue[closed];
&&&&&&&&&&&&&&&&if( !Inqueue[tmp-&key] ){
&&&&&&&&&&&&&&&&&&&&Inqueue[tmp-&key] =
&&&&&&&&&&&&&&&&&&&&open++;
&&&&&&&&&&&&&&&&&&&&queue[open] = tmp-&
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
&&&&&&&&&&&&tmp = tmp-&
&&&&}while(closed & open);
然后是邻接矩阵的：
void SPFA(){
&&&&for( int i=1; i&= i++){
&&&&&&&&Dist[i] = 100000;
&&&&&&&&for( int j=1; j&= j++)
&&&&&&&&&&&&if( !Graph[i][j] && i!=j) Graph[i][j] = 100000;
&&&&int closed = 0, open = 1;
&&&&queue[1] = S;
&&&&Dist[S] = 0;
&&&&&&&&closed++;
&&&&&&&&int u = queue[closed];
&&&&&&&&Inqueue[u] =
&&&&&&&&for(int i=1; i&= i++)
&&&&&&&&&&&&if ( Dist[i] & Dist[u] + Graph[u][i] ){
&&&&&&&&&&&&&&&&Dist[i] = Dist[u] + Graph[u][i];
&&&&&&&&&&&&&&&&Path[i] =
&&&&&&&&&&&&&&&&if( !Inqueue[i] ){
&&&&&&&&&&&&&&&&&&&&Inqueue[i] =
&&&&&&&&&&&&&&&&&&&&open++;
&&&&&&&&&&&&&&&&&&&&queue[open] =
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
&&&&}while(closed & open);
spfa算法 Easy sssp 收藏
输入数据给出一个有N(2 &= N &= 1,000)个节点，M(M &= 100,000)条边的带权有向图.
要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路.
如果存在负权回路, 只输出一行-1;
如果不存在负权回路, 再求出一个点S(1 &= S &= N)到每个点的最短路的长度. 约定: S到S的距离为0, 如果S与这个点不连通, 则输出NoPath.
第一行: 点数N(2 &= N &= 1,000), 边数M(M &= 100,000), 源点S(1 &= S &= N);
以下M行, 每行三个整数a, b, c表示点a, b(1 &= a, b &= N)之间连有一条边, 权值为c(-1,000,000 &= c &= 1,000,000)
如果存在负权环, 只输出一行-1, 否则按以下格式输出
共N行, 第i行描述S点到点i的最短路:
如果S与i不连通, 输出NoP
如果i = S, 输出0;
其他情况输出S到i的最短路的长度
题目说的不是很清楚，给出的图不一定是完全联通图，有些是断开的几个图，所以在判断的源点是否有环以外还要分别对不同的点进行spfa呀。再进行分别的判断和输出。
有几个优化：
1.可以先判断是否有负权自环，有则直接输出-1
2.在枚举的过程中，当这个顶点的最短路(d[i])&0时，有负权回路，输出-1.
【参考程序】：
#include&stdio.h&
#include&string.h&
#include&stdlib.h&
long queue[1001],a[1001],psum[1001],dis[1001],l[],cost[];
long n,m,s,i,j;
bool hash[1001],
void spfa(int s)
&&& int head,tail,start,now,i;
&&& for (i=1;i&=n;i++)
&&&&&&& dis[i]=0
&&&&&&& psum[i]=0;
&&&&&&& hash[i]=
&&& head=tail=1;hash[s]=
&&& psum[s]=1;dis[s]=0;queue[1]=s;
&&& while (head&=tail)
&&&&&&& start=queue[(head-1)%n+1];
&&&&&&& hash[start]=
&&&&&&& for (i=1;i&=l[start][0];i++)
&&&&&&&&&&& now=l[start][i];
&&&&&&&&&&& if (dis[now]&dis[start]+cost[start][now])
&&&&&&&&&&& {
&&&&&&&&&&&&&&& dis[now]=dis[start]+cost[start][now];
&&&&&&&&&&&&&&& if (!hash[now])
&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&& hash[now]=
&&&&&&&&&&&&&&&&&&& tail++;
&&&&&&&&&&&&&&&&&&& queue[(tail-1)%n+1]=
&&&&&&&&&&&&&&&&&&& psum[now]++;
&&&&&&&&&&&&&&&&&&& if (psum[now]&n)
&&&&&&&&&&&&&&&&&&& {//记录每个点进队的次数(判断环的关键}
&&&&&&&&&&&&&&&&&&&&&&& bk=
&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&& }
&&&&&&&&&&& }
&&&&&&& head++;
&&&&&&& hash[start]=
&&&&&&& if (dis[s]&0)
&&&&&&& {//判断环的一个优化
&&&&&&&&&&& bk=
&&&&&&&&&&&
void output()
&&& spfa(s);
&&& if (!bk)
&&&&&&& printf("-1\n");
&&& memcpy(a,dis,sizeof(long)*(n+1));
&&& for (i=1;i&=n;i++)
&&&&& if (a[i]==0xfffffff)
&&&&&&&&&&& bk=
&&&&&&&&&&& spfa(i);
&&&&&&&&&&& if (!bk)
&&&&&&&&&&& {
&&&&&&&&&&&&&&& printf("-1\n");
&&&&&&&&&&&&&&&
&&&&&&&&&&& }
&&& for (i=1;i&=n;i++)
&&&&& if (a[i]==0xfffffff) printf("NoPath\n");
&&&&& else printf("%d\n",a[i]);
void input()
&&& scanf("%d%d%d",&n,&m,&s);
&&& for (i=1;i&=n;i++)
&&&&& for (j=1;j&=n;j++)
&&&&&&& if (i==j) cost[i][j]=0;
&&&&&&& else cost[i][j]=0
&&& memset(l,0,sizeof(l));
&&& int x,y,c;
&&& for (i=1;i&=m;i++)
&&&&&&& scanf("%d%d%d",&x,&y,&c);
&&&&&&& if (c&cost[x][y])
&&&&&&&&&&& cost[x][y]=c;
&&&&&&&&&&& l[x][0]++;
&&&&&&&&&&& l[x][l[x][0]]=y;
int main()
&&& input();
&&& output();
&&& system("pause");
&&& return 0;
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/bobcowwocb/archive//4550188.aspx
SPFA即shotest path faster algorithm，由意思就可以看出该算法效率比较高。
其实SPFA就是bellman-ford算法的一个优化。
具体做法是用一个队列保存待松弛的点，然后对于每个出队的点依次遍历每个与他有边相邻的点（用邻接表效率较高），如果该点可以松弛并且队列中没有该点则将它加入队列中，如此迭代直到队列为空。
据说平均效率是O（E），可见对边稀疏的图用此算法效果是相当可观的。
若要判负环路,则记录一个点的入队次数,若超过边数，则有负权环。
#include&&iostream&
#include&&queue&
using&namespace&
const&long&MAXN=<span style="color: #000;
const&long&lmax=<span style="color: #x7FFFFFFF;
typedef&struct&&
&&&&long&v;
Edge&e[MAXN];
long&p[MAXN];
long&Dis[MAXN];
bool&vist[MAXN];
queue&long&&q;
long&m,n;//点,边
void&init()
&&&&long&i;
&&&&long&eid=<span style="color: #;
&&&&memset(vist,<span style="color: #,sizeof(vist));
&&&&memset(p,-<span style="color: #,sizeof(p));
&&&&fill(Dis,Dis+MAXN,lmax);
&&&&while&(!q.empty())
&&&&&&&&q.pop();
&&&&for&(i=<span style="color: #;i&n;++i)
&&&&&&&&long&from,to,
&&&&&&&&scanf("%ld&%ld&%ld",&from,&to,&cost);
&&&&&&&&e[eid].next=p[from];
&&&&&&&&e[eid].v=
&&&&&&&&e[eid].cost=
&&&&&&&&p[from]=eid++;
&&&&&&&&//以下适用于无向图
&&&&&&&&swap(from,to);
&&&&&&&&e[eid].next=p[from];
&&&&&&&&e[eid].v=
&&&&&&&&e[eid].cost=
&&&&&&&&p[from]=eid++;
void&print(long&End)
&&&&//若为lmax&则不可达
&&&&printf("%ld\n",Dis[End]);&&&&
void&SPF()
&&&&init();
&&&&long&Start,E
&&&&scanf("%ld&%ld",&Start,&End);
&&&&Dis[Start]=<span style="color: #;
&&&&vist[Start]=true;
&&&&q.push(Start);
&&&&while&(!q.empty())
&&&&&&&&long&t=q.front();
&&&&&&&&q.pop();
&&&&&&&&vist[t]=false;
&&&&&&&&long&j;
&&&&&&&&for&(j=p[t];j!=-<span style="color: #;j=e[j].next)
&&&&&&&&&&&&long&w=e[j].
&&&&&&&&&&&&if&(w+Dis[t]&Dis[e[j].v])
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&Dis[e[j].v]=w+Dis[t];
&&&&&&&&&&&&&&&&if&(!vist[e[j].v])
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&vist[e[j].v]=true;
&&&&&&&&&&&&&&&&&&&&q.push(e[j].v);
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
&&&&print(End);
int&main()
&&&&while&(scanf("%ld&%ld",&m,&n)!=EOF)
&&&&&&&&SPF();
&&&&return&<span style="color: #;
<span class="diggnum" id="digg_count_
<span class="burynum" id="bury_count_
(请您对文章做出评价)
一、Bellman-Ford算法
最优性原理
它是最优性原理的直接应用，算法基于以下事实：
l&&&&&&&&& 如果最短路存在，则每个顶点最多经过一次，因此不超过n-1条边；
l&&&&&&&&& 长度为k的路由长度为k-1的路加一条边得到；
l&&&&&&&&& 由最优性原理，只需依次考虑长度为1，2，&#8230;，k-1的最短路。
适用条件&范围
l&&&&&&&&& 单源最短路径(从源点s到其它所有顶点v);
l&&&&&&&&& 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
l&&&&&&&&& 边权可正可负(如有负权回路输出错误提示);
l&&&&&&&&& 差分约束系统（需要首先构造约束图，构造不等式时&=表示求最小值, 作为最长路，&=表示求最大值, 作为最短路。&=构图时, 有负环说明无解；求不出最短路（为Inf）为任意解。&=构图时类似）。&&
l&&&&&&&&& 对每条边进行|V|-1次Relax操作;
l&&&&&&&&& 如果存在(u,v)&#8712;E使得dis[u]+w&dis[v],则存在负权回路;否则dis[v]即为s到v的最短距离,pre[v]为前驱。&&
时空复杂度&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
for i:=1 to |V|-1 do
&&& for 每条边(u,v)&#8712;E do&& Relax(u,v,w);
for每条边(u,v)&#8712;E do
if dis[u]+w&dis[v] Then Exit(False)
算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，仍不失为一个很实用的算法。
改进和优化&& 如果循环n-1次以前已经发现不存在紧边则可以立即终止； Yen氏改进（不降低渐进复杂度）；SPFA算法
二、&&&&&&&&&&&& SPFA算法
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。 它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
SPFA对Bellman-Ford算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的 改变。因此，算法大致流程是用一个队列来进行维护，即用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点s入队。当队列不为空时，取出队首顶点， 对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其入队。经过有限次的松弛操作后，队列将为空，算法结束。SPFA算法的实 现，需要用到一个先进先出的队列 queue 和一个指示顶点是否在队列中的标记数组mark。为了方便查找某个顶点的邻接点，图采用临界表存储。
Procedure SPFA;Begin&&&&&&&&&&&& initialize-single-source(G,s);&&&&&&&&&&&& initialize-queue(Q);&&&&&&&&&&&& enqueue(Q,s);&&&&&&&&&&&& while not empty(Q) do begin&&&&&&&&&&&&&&& u:=dequeue(Q);&&&&&&&&&&&&&&& for each v&#8712;adj[u] do begin&&&&&&&&&&&&&&&&&& tmp:=d[v]; relax(u,v);&&&&&&&&&&&&&&&&&& if (tmp&&d[v]) and (not v in Q) then enqueue(v);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&E负环处理
&& 需要特别注意的是：仅当图不存在负权回路时，SPFA能正常工作。如果图存在负权回路，由于负权回路上的顶点无法收敛，总有顶点在入队和出队往返，队列无法为空，这种情况下SPFA无法正常结束。
判断负权回路的方案很多，世间流传最广、比较容易实现并且高效的方法的是记录每个结点进队次数，超过|V|次表示有负权。
三、&&&&&&&&&&&& 学以致用
POJ 1201 Intervals 差分约束系统
设S(i)为 0..i-1 中在最终序列中的的整数个数。则约束条件如下:
S(b)-S(a) &= c
0 &= S(i+1) - S(i) &= 1 &==& S(i+1)-S(i) &= 0;
&&&&&&&&&&&&&&&&&&&&&&&&&&&& S(i)-S(i+1) &= -1
注意本题要求的是最小值, 而按照&=号建图后发现图中有负环, 怎么办呢?
其实很简单, 本题求的不是最短路, 而是最长路! Bellman_ford即可!
POJ 1275 Cashier Employment 出纳员的雇佣
黑书上有详细讲解
POJ 1364 King 差分约束系统
这个题目构图之后, 只需要用bellman_ford判断是否有负圈.
首先进行转换:a[j]+...+a[j+m] = a[1]+...a[j+m] - (a[1]+...+a[j-1]) = sum[j+m] -
sum[j-1] &(&) ki. 差分约束只能全部是&=或者(&=).
第二步转换: sum[j+m]-sum[j-1] &= ki-1 或者 sum[j-1]-sum[j+m] &= -ki-1.
约束图构造好后就是简单的Bellman-Ford了!
POJ 1716 Integer Intervals 是1201的简单版本, 贪心算法能够得到更好的效果.
POJ 2983 Is the Information Reliable?
差分约束题, 处理一下等号的情况, 然后普通的Bellman_ford
POJ 3159 Candies 最短路径
Bellman-Ford超时, Dijkstra算法可以高效解决, SPFA(队列)居然超时...SPFA修改为堆栈实现就过了.
POJ 3169 Layout 差分约束
Bellman-Ford 和 SPFA 实现均可
POJ 3259 Wormholes 判断负权回路
TOJ 2976 Path 单纯的最短路径 可练习SPFA
ZOJ 3033 Board Games 我做的第一道Bellman-Ford题目
首先，DFS判断可达性，不可达直接输出infinity结束，可达，bellman-ford判断是否存在负环，存在输出infinity，否则，输出最短距离。
SPFA即shotest path faster algorithm，由意思就可以看出该算法效率比较高。
其实SPFA就是bellman-ford算法的一个优化。
具体做法是用一个队列保存待松弛的点，然后对于每个出队的点依次遍历每个与他有边相邻的点（用邻接表效率较高），如果该点可以松弛并且队列中没有该点则将它加入队列中，如此迭代直到队列为空。
据说平均效率是O（E），可见对边稀疏的图用此算法效果是相当可观的。
若要判负环路,则记录一个点的入队次数,若超过边数，则有负权环。
#include&&iostream&
#include&&queue&
using&namespace&
const&long&MAXN=<span style="color: #000;
const&long&lmax=<span style="color: #x7FFFFFFF;
typedef&struct&&
&&&&long&v;
Edge&e[MAXN];
long&p[MAXN];
long&Dis[MAXN];
bool&vist[MAXN];
queue&long&&q;
long&m,n;//点,边
void&init()
&&&&long&i;
&&&&long&eid=<span style="color: #;
&&&&memset(vist,<span style="color: #,sizeof(vist));
&&&&memset(p,-<span style="color: #,sizeof(p));
&&&&fill(Dis,Dis+MAXN,lmax);
&&&&while&(!q.empty())
&&&&&&&&q.pop();
&&&&for&(i=<span style="color: #;i&n;++i)
&&&&&&&&long&from,to,
&&&&&&&&scanf("%ld&%ld&%ld",&from,&to,&cost);
&&&&&&&&e[eid].next=p[from];
&&&&&&&&e[eid].v=
&&&&&&&&e[eid].cost=
&&&&&&&&p[from]=eid++;
&&&&&&&&//以下适用于无向图
&&&&&&&&swap(from,to);
&&&&&&&&e[eid].next=p[from];
&&&&&&&&e[eid].v=
&&&&&&&&e[eid].cost=
&&&&&&&&p[from]=eid++;
void&print(long&End)
&&&&//若为lmax&则不可达
&&&&printf("%ld\n",Dis[End]);&&&&
void&SPF()
&&&&init();
&&&&long&Start,E
&&&&scanf("%ld&%ld",&Start,&End);
&&&&Dis[Start]=<span style="color: #;
&&&&vist[Start]=true;
&&&&q.push(Start);
&&&&while&(!q.empty())
&&&&&&&&long&t=q.front();
&&&&&&&&q.pop();
&&&&&&&&vist[t]=false;
&&&&&&&&long&j;
&&&&&&&&for&(j=p[t];j!=-<span style="color: #;j=e[j].next)
&&&&&&&&&&&&long&w=e[j].
&&&&&&&&&&&&if&(w+Dis[t]&Dis[e[j].v])
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&Dis[e[j].v]=w+Dis[t];
&&&&&&&&&&&&&&&&if&(!vist[e[j].v])
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&vist[e[j].v]=true;
&&&&&&&&&&&&&&&&&&&&q.push(e[j].v);
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
&&&&print(End);
int&main()
&&&&while&(scanf("%ld&%ld",&m,&n)!=EOF)
&&&&&&&&SPF();
&&&&return&<span style="color: #;
今天终于用SPFA写出了第一个程序，感觉收获很大，从Dij到Floyed再到Bellmen，以及今天的SPFA，每一种算法背后都蕴藏着许多值得思考的地方。正因为研究了它们，才使得我的能力不断地获得了提高。
之前以为SPFA做为最短路问题最快的算法，想必代码定不好写，不过今天研究过才知道，SPFA的代码量远远不及Dij，这着实令人惊叹，原来最好的算法SPFA是如此的好写，呵呵 我想此算法在很大程度上可以完全代替之前的算法，以后再碰到最短路问题时，SPFA一定能成为首要的选择！
PS:由于是用邻接表来存储的，所以每次操作前要收回以前分配的内存，我尝试了收回和不收回两种方法，发现其实差别不大，如果纯粹是比赛的话，可能不收回反而会更好些（避免超时）。当然如果在实际应用中，应该切记内存的分配，否则软件可能会发生异常。
//Coded&by&abilitytao&
//Time:&22:49:58
#include&iostream&
#include&cmath&
#include&queue&
using&namespace&
#define&MAX_NUM&
#define&MAX_DOTNUM&1000001
queue&int&
bool&mark[MAX_DOTNUM];
__int64&dis[MAX_DOTNUM];
struct&node
&&&&int&v;
&&&&int&w;
&&&&node&*
}edge[MAX_DOTNUM];//此邻接表用于存储正向图
node&reversed_edge[MAX_DOTNUM];//此逆邻接表用于存储逆向图
void&initial(node&edge[])//邻接表的初始化，里面封装了回收上一次操作所分配之内存的操作
&&&&int&i;
&&&&node&*p;
&&&&node&*q;
&&&&for(i=<span style="color: #;i&=n;i++)
&&&&&&&&p=&edge[i];
&&&&&&&&q=p-&
&&&&&&&&while(q!=NULL)
&&&&&&&&&&&&p-&next=q-&
&&&&&&&&&&&&delete&q;
&&&&&&&&&&&&q=p-&
void&input_case()//每一个case的输入函数
&&&&int&i;
&&&&for(i=<span style="color: #;i&=m;i++)
&&&&&&&&node&*p;
&&&&&&&&node&*q;
&&&&&&&&int&a,b,c;
&&&&&&&&scanf("%d%d%d",&a,&b,&c);
&&&&&&&&/**/////////////////////////
&&&&&&&&p=&edge[a];
&&&&&&&&q=new&
&&&&&&&&q-&v=b;
&&&&&&&&q-&w=c;
&&&&&&&&q-&next=p-&
&&&&&&&&p-&next=q;
&&&&&&&&/**/////////////////////////
&&&&&&&&p=&reversed_edge[b];
&&&&&&&&q=new&
&&&&&&&&q-&v=a;
&&&&&&&&q-&w=c;
&&&&&&&&q-&next=p-&
&&&&&&&&p-&next=q;
void&spfa(node&edge[])//SPFA部分
&&&&int&i;
&&&&/**////////////////////////////////////////////////////////////////
&&&&memset(mark,false,sizeof(mark));
&&&&for(i=<span style="color: #;i&=n;i++)
&&&&&&&&dis[i]=MAX_NUM;
&&&&while(myqueue.size()!=<span style="color: #)
&&&&&&&&myqueue.pop();
&&&&/**////////////////////////////////////////////////////////////
&&&&dis[<span style="color: #]=<span style="color: #;
&&&&mark[<span style="color: #]=true;
&&&&myqueue.push(<span style="color: #);
&&&&while(myqueue.size()!=<span style="color: #)//如果队列不空，则进行松弛操作，直到队列空为止
&&&&&&&&int&temp=myqueue.front();
&&&&&&&&myqueue.pop();
&&&&&&&&mark[temp]=false;
&&&&&&&&node&*p;
&&&&&&&&for(p=edge[temp].p!=NULL;p=p-&next)
&&&&&&&&&&&&if(dis[p-&v]&dis[temp]+p-&w)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&dis[p-&v]=dis[temp]+p-&w;
&&&&&&&&&&&&&&&&if(mark[p-&v]!=true)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&myqueue.push(p-&v);
&&&&&&&&&&&&&&&&&&&&mark[p-&v]=true;
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
int&main()
&&&&int&i,j;
&&&&__int64&
&&&&scanf("%d",&testcase);
&&&&for(i=<span style="color: #;i&=MAX_DOTNUM-<span style="color: #;i++)
&&&&&&&&edge[i].v=i;
&&&&&&&&edge[i].w=<span style="color: #;
&&&&&&&&edge[i].next=NULL;
&&&&for(i=<span style="color: #;i&=MAX_DOTNUM-<span style="color: #;i++)
&&&&&&&&reversed_edge[i].v=i;
&&&&&&&&reversed_edge[i].w=<span style="color: #;
&&&&&&&&reversed_edge[i].next=NULL;
&&&&for(i=<span style="color: #;i&=i++)
&&&&&&&&sum=<span style="color: #;
&&&&&&&&scanf("%d%d",&n,&m);
&&&&&&&&initial(edge);
&&&&&&&&initial(reversed_edge);
&&&&&&&&input_case();
&&&&&&&&spfa(edge);
&&&&&&&&for(j=<span style="color: #;j&=n;j++)
&&&&&&&&&&&&sum+=dis[j];
&&&&&&&&spfa(reversed_edge);
&&&&&&&&for(j=<span style="color: #;j&=n;j++)
&&&&&&&&&&&&sum+=dis[j];
&&&&&&&&printf("%I64d\n",sum);
&&&&system("pause");
&&&&return&<span style="color: #;登录网易通行证
使用网易通行证(含网易邮箱)帐号登录
提交您的投诉或建议
视频画面花屏
视/音频不同步
播放不流畅
登录后才能查看我的笔记
暂时没有笔记!
确定删除笔记？
即将播放下一集，请您保存当前的笔记哦！
对字幕纠错要登录哦！
内容不能少于3个字
课程简介及算法分析
渐近符号、递归及解法
分治法（1）
快排及随机化算法
线性时间排序
顺序统计、中值
本课为我们引入了一种简单而高效的数据结构——哈希表（又译作散列表）。课堂上，教授为我们介绍了哈希表的基础知识，讲述除法哈希法、乘法哈希法以及开放寻址法，并对它的复杂度做了分析。除此之外，他还就如何高效地运用哈希表、如何处理可能遇到的“碰撞”问题等进行了讨论。
本课继续深入学习哈希表，这节课的内容主要是哈希表的高级运用。为了应对哈希表发生“碰撞”的问题，教授这次给我们带来了全域哈希和完全哈希。这节课里涉及到了很多美妙的数学知识，算法的证明过程相当有趣。学习这节课的内容，将会使你的哈希表更为高效、更为稳定。
本课为我们带来了一种常用的数据结构——二叉搜索树。这种数据结构有着媲美快速排序的速度，同时又能完成插入、删除和查找等动态化的操作，高效而又易于实现。教授将在本节课为我们讲解二叉搜索树的原理，运用巧妙的数学知识来证明它的高效性。二叉搜索树有什么优缺点，随机化二叉树又如何解决问题，这节课都会一一为你解答。
如果搜索树的结构不能保持平衡，它的运行效率将会大打折扣。这节课上，我们将会着重学习一种著名而实用的平衡树算法——红黑树。教授将会从红黑树的运行效率入手，再扩展到实际构造和维护红黑树。讲解过程中加入了大量的图例，更加方便大家消化吸收。
在实践中，我们对数据结构的功能需求并不仅仅局限于基本的插入、删除和查询操作。为了使数据结构能满足我们的需求，第11课里，教授给我们讲授了如何扩展一个现有的数据结构。教授以红黑树的几种扩展算法为例，讲解了的扩展的方法论以及策略。掌握了这些以后，你实现新功能起来将会更加得心应手。
《算法导论》第12课里我们将学到一种简单而又十分有趣的动态搜索数据结构——跳跃表。这种数据结构的优势在于它易于实现，而且很好地保证了它总是能高效运作。教授通过纽约地铁的例子引入，生动地讲解了跳跃表的构造、查询过程。同时，他给我们分析了跳跃表“有高概率”的高效性质，用数学给我们展示了它的强大之处。
有时候，就算是再大的困难，只要人人都愿意出一份力，也能大事化小。而算法的分析也有这种情况。有时候某几步操作相当复杂，但是如果将一系列操作平均起来，它的代价可能也并不是那么的高。《算法导论》第13课里，教授就给我们讲授了几种平摊分析的方法，包括聚集法、记账法还有势能法。这些都是算法分析的重要方法，掌握它们将能让我们更加准确地评估算法优劣性。
我们将要关注一种在线算法的分析方法——竞争分析。实际应用中，数据不会总是全部出现在我们面前，而是一个接一个地出现。这样我们就不能安排最好的对策来处理问题。但是我们也可以证明，在线算法并不会跟最优算法差太远。这节课上，教授将会结合上一节课中平摊分析的内容，给我们展示这一个相当精彩的分析过程。
我们将会学到一个常用的优化算法的技术——动态规划。它是一种解决最优解问题的一种方法，它还是信息竞赛选手必须掌握的技能。在这一节课上，教授会围绕最长公共子序列（LCS）的实现问题来讲解可动态规划算法的特征，还有动态规划的一般优化思路和方法。通过应用动态规划，我们的程序性能将会获得显著的提升。
《算法导论》第16课中，教授给我们带来了一种新的算法思想－－贪婪算法的思想。和动态规划一样，贪婪算法是一种求解最优问题的方法。它强调通过寻找局部的最优解，从而节省大量的时间和资源。这次课里，教授会围绕图的最小生成树的问题，分析贪婪算法的思想和应用条件。我们还会看到一个贪婪算法实例－－Prim算法，看看它又是如何为AT＆T公司取得垄断的地位。
从第17节的《算法导论》开始，MIT的教授将会为我们上演精彩的最短路径三部曲。在第一乐章里，我们会学习到一个非常著名的求解最短路径算法－－Dijkstra算法。教授首先会给我们讲解最短路径的特殊性质，然后针对一种非负权值的的最短路径问题，给我们详细讲解Dijkstra算法的做法，以及对它的正确性进行深度的分析。
承接上一回，《算法导论》第18集是最短路径三部曲的第二乐章。在这一节课上，教授给我们讲解的是能够处理负权值最短路径问题的算法——Bellman-Ford算法。Bellman-Ford算法不仅能够检测图中的负权环，同时它还能解决线性规划的差分约束问题。教授将给我们详细讲解Bellman-Ford算法的流程，并证明它的正确性。这些内容都会跟下一节课的内容息息相关。
[第19课]最短路径算法：点的最短路径
《算法导论》的第19课终于到了最短路径三部曲的高潮。这次我们将会着眼于全点对最短路径问题，教授将会给我们用三种算法来解决这个问题。除了上节课我们学到Bellman-Ford，我们还会用一个精彩的技巧，将问题与矩阵乘法联系起来，也就是Floyd-Warshall算法。而最后，我们将会学习最强大的Johnson算法，来为最短路径三部曲唱响最华丽的解答。
《算法导论》课程的最后将介绍一些高级课题。本课介绍的是并行算法。解答了1、面对多核处理器技术的不断革新，对算法如何优化，使得效率可以倍增；2、如何来分析并行算法对运行速度的提升；3、著名的国际象棋人工智能“深蓝”曾经的宿敌是谁。
《算法导论》第23课将承接上一回，这一次教授将给我们介绍并行算法的实际应用，讲解如何使用多线程来实现算法的并行化。课上教授将会用矩阵相乘以及归并排序为例子，从算法框架到运行时间分析来教大家实际认识多线程并行算法。
承接上一课，本课教授介绍了缓存敏感算法和缓存参数无关算法的概念，首先从计算机的缓存-内存分层存储模型引入，讨论了缓存参数无关算法的性质和分析上的优越性，并且具体讨论了在分层存储模型中的算法性能分析和存储设计。
《算法导论》课程的最终章将继续深入分析缓存参数无关算法，教授将在本次课上为我们讲解多路归并排序算法是如何与缓存参数无关算法模型相结合。他将用一种名为K漏斗的特殊数据结构从实现到分析来给我们展示如何更高效地利用缓存来优化算法设计。
跟贴热词：
文明上网，登录发贴
网友评论仅供其表达个人看法，并不表明网易立场。
学校：麻省理工学院
讲师：Charles Leiserson&Erik Demaine
授课语言：英文
类型：计算机 国际名校公开课
课程简介：本课程教授高效率算法的设计及分析技巧，并着重在有实用价值的方法上。课程主题包含了：排序、搜寻树、堆积及散列；各个击破法、动态规划、偿还分析、图论算法、最短路径、网络流、计算几何、数字理论性算法；多项式及矩阵的运算；高速缓存技术及并行运算。
扫描左侧二维码下载客户端}