聚龙外国语学校暑假集训Day6——7.21

Posted on By 郑, 铭轩 聚龙外国语学校暑假集训Day6——7.21无评论

吃完早餐后，我们又走了200多米的路程，从宿舍来到了教室听图论。

最短路径算法之一的“Floyd”算法(求任意两点之间的距离）。在我看来这个算法就是暴力循环。一个个的去枚举。

一.“Floyd”算法

具体思想如下：
a[i][j]表示为i到j的最短距离
有一个数组如下：

0 5 8 ∞ 3
5 0 2 ∞ 6
8 2 0 10 4
∞ ∞ 10 0 11
3 6 4 11 0

其中数字表示i到j的距离，‘∞’（也可以设为999999）表示i无法直接到j
我们假设i到j的距离不只是直接到达，而是有经过另外一些点，再到j点。
k从1开始，一直到n。表示i经过k到j
方程如下：

if(a[i][j]>a[i][k]+a[k][j])
{
    a[i][j]=a[i][k]+a[k][j];
}

或

a[i][j]=min(a[i][j],a[i][k]+a[k][j]);

等k遍历完后,a[i][j]就表示为i到j的最短距离
具体代码如下：

for(int k=1;k<=m;k++)
{
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
        }
    }
}

Path数组初始化

for(int i=1;i<=n;i++)
｛
    for(int j=1;j<=n;j++)
    ｛
        if(e[i][j]<inf && i!=j)
            path[i][j]=i;
        else
            path=-1;
    ｝
｝

首先，第一个：

二.“Dijkstra”算法

它的限定要求是边权值非负，也就是 w[i]>0 时才可以使用它
And它的时间是O(N²),so N最好也要小于 10000，或更小才可以使用。

它的主要思想如下：

首先求出一条长度最短的最短路径，再参照它求出长度次短的一条最短路径，以此类推，直到从源点v0到其他各个顶点的最短路径全部被求出为止（是基于贪心思想的）

具体思想过程：

首先，先设置3个数组，dis，S，path 3个数组

dis[ i ]：表示i点到源点v0的最短路长度，初始化dis[i]=e[v0][i]

S[ i ]：为0表示顶点i还未加入S， S[i]为1表示i已经加入S中，初始化S[v0]为1，其余为0，表示最初集合S中只有源点v0

path[ i ]:表示v0到i的最短路径上顶点i的前一个顶点序号（即前驱）。通过这个数组可以确定v0到i的最短路径上的每一个顶点

然后，再在数组dis[ i ]里查找S[ i ]!=1，并且dis[ i ]最小的顶点k
将S[ k ]改为1，表示 k 已经加入S集合中。即已经找到源点v0到点k的最短路径了。
修改T集合中每个顶点 j 的dis和path数组元素值：当S[ j ]！=1，且k到顶点 j 有dis[ k ]+e[ k ][ j ]<dis[ j ]，更新dis[ j ] 为dis[ k ]+e[ k ][ j ]，修改path[ j ]为k。
可以理解为因为v0到k的最短路径已经找到了，所以我们可以试图通过k中转一下走到j来尝试这会不会是v0到j的最短路径

具体代码如下：

（1）定义

const int N = 1001;
int n, m;
int g[N][N];
int dist[N];
bool st[N];

（2）读入

scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while(m --){
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    g[a][b] = min(g[a][b], c);
}

（3）主体框架

int dijkstra(){
    memset(dist, 0x3f, sizeof dist); //dist数组初始化为无穷大
    dist[1] = 0;
    for(int i = 0; i < n; i ++){
        int t = -1; //初始化为表示还没有确认，在下面的循环中找到dis最小且还没被标记过的点
        for(int j = 1; j  dist[j])){
                t = j;
            }
        }
        st[t] = true;//标记点t已经找到最短路径了
        for(int j = 1; j <= n; j ++){
            dist[j] = min(dist[j], dist[t] + g[t][j]);//通过点t中转
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}//dist中隐含了多重中转

当然，只是这样打并不是这个算法的最优版本，还可以适当的优化一下。

优化版本的思想如下：

（1）存储方式

堆优化的时间复杂度是O((N+M)logN)，这时不该用邻接矩阵来存图了，要使用邻接表，不然空间复杂度变成了O(N2)，优化时间的复杂度就没有任何意义了。

（2）如何实现堆

用STL中的priority_queue或者set来实现堆，set可以看做一个从小到大有序的序列，支持插入、删除查找。这里我们只需要使用插入、查询头元素和删除头元素。

（3）具体代码

（I）

（II）

(III)

接着，第二个：

三.“Bellman-Ford”算法

（1）优点

其优于“Dijkstra”算法的方面是边的权值可以为负数、实现简单 。

（2）缺点

无法处理存在负权回路的情况。

（3）算法时间复杂度

O(NM)，其中N是顶点数，M是边数。

（4）主体思想

（I）

设v0为起点，dis[ i ]为v0到i的最短距离（dis 数组的作用和“dijkstra” 算法一样），path[ i ]为i点的前驱节点。

（II）

u[i]、v[i]、w[i]三个数组用来记录边的信息，表示从顶点u[i]到顶点v[i]这条边（u[i] –> v[i]）权值为w[i]

（III）

初始化：dis[v0]=0,dis[ i ]=∞（i≠v0）

（IV）

看看能否通过u[i]—>v[i] （权值为w[i]）这条边，使源点到vi号顶点的距离变短。即源点到u[i]号顶点的距离（dis[u[i]]） 加上 u[i] —> v[i]这条边（权值为w[i]）的值是否比原来源点到v[i]号点距离（dis[v[i]]）要小。

（5）核心代码

for(k=1;k<=n-1;k++)     //进行n-1轮松弛
{
    for(i=1;i<=m;i++)       //枚举所有边，判断能否松弛
        if(dis[u[i]]+w[i]<dis[v[i]])
        {
            dis[v[i]]=dis[u[i]]+w[i];
            path[v[i]]=u[i];
        }
}

（6）算法代码小优化

（I）改进思想

未必一定要循环n-1次，只要在某次循环过程中，考虑每条边后，都没能改变当前源点到所有顶点的最短路径长度，那么Bellman-Ford算法就可以提前结束了

（II）改进代码

for(k=1;k<=n-1;k++)                 //进行n-1轮松弛
{
    int flag=0;
    for(i=1;i<=m;i++)                    //枚举所有边
        if(dis[u[i]]+w[i]<dis[v[i]])   //u[i]、v[i]分别是这条边连接的两个点
        {
            dis[v[i]]=dis[u[i]]+w[i];
            flag=1;
        }
    if(flag==0) break;
}

最后，第三个：

四.“SPFA”算法

（1）思想

从“Bellman-Ford”算法可以得到启发：每次仅对最短路估计值发生变化了的顶点的所有出边执行松弛操作。but，如何知道当前哪些点的最短路程发生了变化呢？可以用一个队列来维护这些点。这就是SPFA(Shortest Path Faster Algorithm)算法，国际上通称为“队列优化的‘Bellman-Ford’算法”。

即每次只将在本次松弛中最短路发生变化的点加入队列中

（2）时间复杂度

SPFA的复杂度为O(km), k为所有顶点进队的平均次数，可以证明k一般小于等于2；能处理负边，无法处理负权回路；不稳定，复杂度可能到O(nm)

（3）算法流程

（I）

记源点为v0，vst[ ]记录点是否在队列中，距离值为dis[ ]。

（II）

初始化：dis[v0]=0，其他点的距离为∞；将源点v0入队，vst[ v0 ]=1

（III）

从队首取出点k，扫描所有由 k 结点可以一步到达的结点；一旦发现有结点 j 可以松弛，更新dis[ j ]的值，再检查j当前是否在队列中，如果不在，就将 j 入队。
重复执行步骤②，直到队列为空

(4)具体代码

（I）使用邻接表来存图

scanf("%d%d%d",&n,&m,&v0);
for(int i=1;i<=n;i++) head[i]=-1;
for(int i=1;i<=m;i++)
{
    scanf("%d%d%d",&u[i],&v[i],&w[i]);
    next[i]=head[u[i]];
    head[u[i]]=i;
}

（II）初始化部分

void spfa(int v0)
{
    queue q;
    for(int i=1;i<=n;i++)
    {
        dis[i]=inf;
        vst[i]=0;
    }
    dis[v0]=0;
    q.push(v0);
    vst[v0]=1; //源点入队并标记
    ｝

（III）队列处理部分

while(!q.empty())
{
    int k=q.front();         //取队首
    q.pop();vst[k]=0;       //出队并标记
    for(int i=head[k];i!=-1;i=next[i]) //遍历领接表
    {
        if(dis[v[i]]>dis[k]+w[i])
        {
            dis[v[i]]=dis[k]+w[i];
            if(vst[v[i]]==0)    //未入队
            {
                q.push(v[i]); vst[v[i]]=1;  //标记入队
            }
        }
    }
}

（IV）输出答案

spfa(v0);
for(int i=1;i<=n;i++)
{
    if(i==v0) printf("0 ");
    else if(dis[i]<inf) printf("%d ",dis[i]);
    else printf("2147483647 ");
}

four个算法总结+优化

五.最小生成树

很简单，就不再详细讲了。我也是都听懂了，较昨天的简单。

下午，我们打了s组的比赛，我也是拿下了16的“高”分
晚上，我j组打了3题，s改出来0题，还行吧。（比之前差）
这就是美妙的第六天。
（不过学校小卖铺还是没开，not happy）

训练日志

发表回复