NOIP专题复习1 图论-最短路

今天我们要复习的内容是图论中的最短路算法，我们在这里讲3种最短路求法，分别是：floyd，dijkstra，spfa。
那么我们从一道例题来切入今天讲解的算法。

一、典型例题

1、热浪

题目描述

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

输入输出格式

输入格式：
第一行: 4个由空格隔开的整数: T, C, Ts, Te
第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci

输出格式：
一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。

输入输出样例

输入样例#1：

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

输出样例#1：

7

说明

【样例说明】
5->6->1->4 (3 + 1 + 3)

2、城市路

时间限制: 1 Sec 内存限制: 128 MB

题目描述

罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。

现在给出直接相邻城市的路长度，罗老师想知道从城市1到城市n，最短多少距离。

输入

输入n, m，表示n个城市和m条路
接下来m行，每行a b c， 表示城市a与城市b有长度为c的路

输出

输出1到n的最短路
如果1到达不了n，就输出-1

样例输入

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

样例输出

90

提示

【数据规模和约定】
1<=n<=2000
1<=m<=10000
0<=c<=10000

二、算法分析

（一）dijkstra算法（对于例题1）

1、算法实现

dijkstra有朴素算法与堆优化的两种。
在这里我们只讲朴素算法。
这个朴素算法非常好写（垃圾的我调了2个小时）

2、时间复杂度

时间复杂度为\(O(N^2)\)

3、代码实现

//O(n2)的朴素dijkstra
#include<bits/stdc++.h>
using namespace std;
int n,m,tx,ty,dis[5005],a[2505][2505];
bool b[5005];
int main()
{
    scanf("%d%d%d%d",&n,&m,&tx,&ty);
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    a[i][j]=100000000;
    for (int i=1;i<=m;i++)
    {
        int x,y,z=0;
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=min(a[x][y],z);
        a[y][x]=min(a[y][x],z);
    }
    for (int i=1;i<=n;i++) 
    {
        dis[i]=a[tx][i];
    }
    dis[tx]=0; 
    b[tx]=true;
    for (int i=1;i<=n-1;i++)
    {
        int minn=100000000;
        int k=0;
        for (int j=1;j<=n;j++)
        {
            if ((!b[j])&&(dis[j]<minn))
            {
                minn=dis[j];
                k=j;
            }
        }
        if (k==0) break;
        b[k]=true;
        for (int z=1;z<=n;z++)//这里不能再用j，我也不知道为什么。这个地方错了2个小时。。。
        {   
            if(a[z][k]<100000000)
            if (dis[k]+a[k][z]<dis[z])
            dis[z]=dis[k]+a[k][z];  
        } 
    }
    printf("%d",dis[ty]);
} 

（二）spfa算法（对于例题2）

spfa算法作为重点且最常用。
在稀疏图或有负边权的图上，Dijkstra就失去用武之地了。此时需要使用spfa算法。

1、算法分析

spfa算法使用一个队列，第一步从源点s开始，把s放进队列。对队列中的每个元素x，广度优先遍历其出边，并针对该元素x的这条出边进行松弛操作。如果松弛可以进行，则把这条出边可达的节点加入队列中。

2、时间复杂度

玄学。\(O（kE）\)。对于随机数据来说复杂度较低。
用邻接矩阵存储会导致spfa算法性能大大降低，故需要使用边表（前向星）存图。

3、代码实现

NOIP专题复习1 图论-最短路

原文：https://www.cnblogs.com/zwcblog/p/9346531.html