注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

最短路径  

2015-12-27 16:05:20|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       最短路径:对在权图G=(V,E),从一个源点s到汇点t有很多路径,其中路径上权和最少的路径,称从s到t的最短路径。
       简单讲:找出连接两个给定点的最低成本路径
==============================例子================================
        有一天,你要去旅游,从广州出发,去北京天安门,于是你会坐火车,你可以先买一张去湖南,再从湖南去北京,也可以直接买去北京的票,或许你先去新疆,再去哈尔滨,最后去北京也可以,现已知各城市到各城市的票价,问你怎么样最省钱(时间不是问题!),或许由于某些特殊情况(铁路局疯了?)去哈尔滨只用1元,再去北京不用钱,呃,该怎么办呢?
==============================分析================================
        例子可能很逗,这时,我们把问题用图论来解决。用专业的语言来说,就是文章开头的那句话
        就是这时就涌现了许多办法,各有各的好处。首先,我们来说明一下,用n代表城市个数(点数),用m代表城市之间有多少种票价(边数)。
        1、Dijkstra  时间(n^2)
        2、SPFA     时间(这里有很多争论,最坏情况好像是(n*m)但是又有人说是n,反正很快。)
        3、Floyd      时间(n^3) 
        4、Bellman-Ford    时间(n*m
       这些都是很具有代表性的算法,其中SPFA是Bellman-Ford的优化。

       吹了牛之后,很好奇怎么做吧,下边先引进两个概念:

一、三角形性质
       设源点s到点x、y的最短路径长度为dis[x]、dis[y]。x与y之间的距离是len[x][y],则有下面的“三角形定理”:
    dis[x] + len[x][y]  >=  dis[y] 
          
 二、松驰
       若在处理过程中,有两点x、y出现不符合“三角形定理”,则可改进一下—松驰:
       if ( dis[x]+len[x][y] < dis[y] )
           dis[y] = dis[x]+len[x][y];
附图:
             最短路径(待续……) - 杨鸿飞 - 一个叫杨鸿飞的人的博客
=============================Dijkstra===============================
有请图片君:
         最短路径(待续……) - 杨鸿飞 - 一个叫杨鸿飞的人的博客
        很鬼畜吧!为什么三角形两边之和大于第三边!!!?不然你以为,这样的话还有难度?好吧,这么说吧,现实生活中,总不能那么精确,就像从广州到哈尔滨,中途一定要转站,不然费用是你出不起的(从广州修到哈尔滨!!),这就证明了松弛这种情况。下面开始分析。

        Dijkstra就是贪心,只不过外国人自恋,用自己名字命名(开玩笑……),首先,请看图片君,反映的是三个点的情况。如果红色点为起始点,到蓝色点的最短距离,怎么求呢?首先红色点绿点蓝点有边连接,这样可初步确定一些距离:
        红点-->绿点,3;红点-->蓝点,8。
       (“-->”为距离)

        这时,我们明目张胆地得到红点绿点的最短距离为3。诶,为什么呢?3比8小呗,那么草率吗?因为我们从图中得知,从红点绿点有两种情况:
        1, 红点-->绿点
         2,红点-->蓝点~~>绿点
      ("~~>"为最短距离)

       这时,我们从中选一个最短的就行了,不过我们已经知道了红点-->绿点为3,小于红点-->蓝点的8,因此不管蓝点~~>绿点是多少都没有红点-->绿点短,好吧,这里有个漏洞,如果存在负边(也许哪天铁路局真的大发慈悲,不单单不收钱,还给我们钱……),这个算法就不成立,不过不要灰心,也很少有题目有负边的,在实际中也很少见。言归正传,这样,我们就可以确定一个最短路径。我们知道了红点~~>绿点就可以利用这个新的条件,再次寻找一些条件,也就是从绿点出发,也可以到达蓝点。这时,红点到蓝点的新的距离为红点~~>绿点-->蓝点也就是3+4也就是7,比原来的8短,就更新,这样,我们就知道了红点~~>蓝点

        模拟了那么多,下面来总结一下规律,首先呢,为了便于思考,我们得有一个叫dis的数组,记录的是从起始点到每一个点的最短距离,刚开始都是无穷大,只有起始点到起始点的距离为0,接下来就一直三件事情,1、找当前初始点到所有的点中最短的一个,就可以确定一个最短距离。  2、用这个最短距离去更新其它点。  3、把该点标记为使用过。

        这里每做一次那三件事,就可以确定一个最短距离,有n个点,就做n次,然而做那三件事也需要n次,所以,Dijkstar算法的时间复杂度为n^2。

==============================Floyd================================
        Floyd,就是动态规划,点i 到 点j 的最短距离就是它们之间经过0个点,经过一个点,经过两个点……直到经过n个点的最短距离中选一个最短的,就行了,其中神奇的是,一个原本需要迭代的最短路径,就可以变成有向无环的可以动态规划的东东。注意,先枚举中间经过的点,在枚举i,j。

=======================Bellman-Ford->SPFA==========================
        Bellman-Ford和SPFA的主要思想都是迭代,只要出现了松弛现象,就继续更新,直到没有松弛为止。这个思路很容易理解,两种算法不同的地方是在更新这里,Bellman-Ford是要检测全部点的松弛现象,这样如果每一条边都要松弛,每次松弛都要更新全部点,这样需要O(点数*边数)。然而SPFA只更新被松弛的点,就会比Bellman-Ford快很多,但具体是多少,就不知道了。

==============================程序================================
Dijkstra:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int oo=1000000000;

vector <int> adjp[110];
vector <int> adjd[110];

int K;
int f[110];
int dis[110];

int main()
{
int n;
scanf("%d%d",&K,&n);
for (int i=0; i<n; i++) //用voctor存储边
{
int x,y,d;
scanf("%d%d%d",&x,&y,&d);

adjp[x].push_back(y);
adjd[x].push_back(d);

adjp[y].push_back(x);
adjd[y].push_back(d);
}

int B,E;
scanf("%d%d",&B,&E);

for (int i=0; i<=K; i++) dis[i]=oo; //初始化
dis[B]=0;

for (int j=0; j<K; j++)
{
int np=0;
for (int i=1; i<=K; i++)
if (f[i]==0 && dis[i]<dis[np]) np=i; //贪心找最短边
f[np]=1;

for (int i=0; i<adjp[np].size(); i++) //松弛
{
int tp=adjp[np][i];

if (f[tp]==1) continue;

int t=dis[np]+adjd[np][i];
dis[tp]=min(dis[tp],t);
}
}
printf("%d",dis[E]);

return 0;
}

SPFA:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int oo=1000000000;
const int mm=1000000;

vector <int> adjp[110];
vector <int> adjd[110];

int dis[110];
int K;
int open[mm+100];

void SPFA(int b)
{
for (int i=1; i<=K; i++) dis[i]=oo;
dis[b]=0;

open[0]=b;

for (int Head=0,Tail=0; Head<=Tail; Head++)
{
int p=open[Head%mm];

for (int i=0; i<adjp[p].size(); i++)
{
int np=adjp[p][i];
int ndis=dis[p]+adjd[p][i];

if (ndis>dis[np]) continue;

dis[np]=ndis;
Tail++;
open[Tail%mm]=np;
}
}
}

int main()
{
int n;
scanf("%d%d",&K,&n);
for (int i=0; i<n; i++)
{
int x,y,d;
scanf("%d%d%d",&x,&y,&d);

adjp[x].push_back(y);
adjd[x].push_back(d);

adjp[y].push_back(x);
adjd[y].push_back(d);
}

int B,E;
scanf("%d%d",&B,&E);

SPFA(B);
printf("%d",dis[E]);

return 0;
}

Floyd:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int oo=1000000000;

int dis[110][110];
int K;

int main()
{
int n,M;
scanf("%d%d%d",&M,&K,&n);

for (int i=1; i<=100; i++)
for (int j=1; j<=100; j++) dis[i][j]=oo;

for (int i=0; i<n; i++)
{
int x,y,d;
scanf("%d%d%d",&x,&y,&d);
dis[x][y]=min(dis[x][y],d);
dis[y][x]=dis[x][y];
}

for (int p=1; p<=K; p++)
for (int i=1; i<=K; i++)
for (int j=1; j<=K; j++)
{
int t=dis[i][p]+dis[p][j];
dis[i][j]=min(dis[i][j],t);
dis[j][i]=dis[i][j];
}

int ans=0;
for (int i=1; i<=n; i++)
if (dis[1][i]<M) ans++;
printf("%d",ans);

return 0;
}


  评论这张
 
阅读(12)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018