迪杰斯特拉算法分析

一般用三种数据结构存图，即邻接矩阵，邻接表，链式前向星

1.邻接矩阵

优点
适合稠密图，编码非常简短，对边的存储，查询，更新等操作又快又简单，只需要一步就能访问和修改。
缺点

• 存储复杂度O(V^2)太高
• 一般情况下不能存储重边

2.邻接表

优点
他的优点是存储效率非常高，只需要与边数成正比的空间，存储的复杂度是O(V+E),几乎已经达到了最优复杂度，而且能存储重边
缺点
编程比邻接矩阵麻烦一些，访问和修改也慢一些

一般用STL的vector（动态数组）实现了邻接表

• 首先对边赋值
• 用e[i]：存第i个结点连接的所有边
• 把边（a，b）存到结点a的邻接表中
• 结点u的邻居有e[u].size()个

3.链式前向星

链式前向星是在邻接表的基础上优化的，对于一些空间极其紧张的题，用链式前向星是最好的，它用静态数组模拟邻接表，没有任何浪费，因此它是空间效率最高的存储的方法

• 对于边而言，边的终点是to，权值是w，下一个边next，起点放在head[]中
• head[u]指向结点u的第一个边的存储位置
• 用cnt记录edge[]的末尾的位置，新加入的边放在末尾
  链式前向星的优点是存储效率高，程序简单，能存储重边，缺点是不方便做删除操作

适用范围
迪杰斯特拉算法适用于——单元最短路径问题，单终点最短距离，单对顶点最短路径问题，每对顶点间最短路径问题

基本思想

• Dijkstra算法：一个安路径长度递增地次序产生最短路径的算法
• 每次扩展一个距离最短的点，更新与其相邻的点的距离
• 当所有边的权值都为正数时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，保住了算法的正确性。如果存在负权值的路径，那么考虑spfa算法跑最短路。
• 有向图和无向图都可以使用这个算法，无向图的每条边可以看成相反的两条边
• 引入松弛操作，让源点s到顶点的距离dis[i]取一个很大的值，然后不断减小dis[i]，当所有的dis[i]不能再减小时，就求出了s到所有点的最短路径。松弛操作的目的就是减小dis[i]的值，如果从s到达i有更优的路径则更新dis[i]。

if (dis[v] > dis[u] + e[i].w)
         {
   
            dis[v] = dis[u] + e[i].w;  //松弛操作
            q.push((node){
   dis[v], v}); //把新遍历的到的点加入堆中
         }

dijkstar的原理与流程

• dijkstra本质上的思想是贪心,它只适用于不含负权边的图.
• 我们把点分成两类,一类是已经确定最短路径的点,称为"白点",另一类是未确定最短路径的点,称为"蓝点"
• 初始化dis[start] = 0,dis[start]=0,其余节点的dis值为无穷大.
• 找一个disdis值最小的蓝点x,把节点x变成白点.
• 遍历x的所有出边(x,y,z),若dis[y] > dis[x] + z,则令dis[y] = dis[x] + z
• 重复2,3两步,直到所有点都成为白点…
• 时间复杂度为O(n^2)

举例
​ 友情提示以下图片参考洛谷—最短路在此鸣谢~
1.(令start = 1)
2.开始时我们把dis[start]初始化为0,其余点初始化为inf

第一轮循环找到dis值最小的点1,将1变成白点,对所有与1相连的蓝点的dis值进行修改,使得dis[2]=2,dis[3]=4,dis[4]=7

第二轮循环找到dis值最小的点2,将2变成白点,对所有与2相连的蓝点的dis值进行修改,使得dis[3]=3,dis[5]=4

第三轮循环找到dis值最小的点3,将3变成白点,对所有与2相连的蓝点的dis值进行修改,使得dis[4]=4

接下来两轮循环分别将4,5设为白点,算法结束,求出所有点的最短路径

为什么dijkstra不能处理有负权边的情况

• 2到3的边权为-4,显然从1到3的最短路径为-2 (1->2->3)…但在循环开始时程序会找到当前dis值最小的点3,并标记它为白点
• 这时的dis[3]=1,然而1并不是起点到3的最短路径.因为3已经被标为白点,所以dis[3]不会再被修改了.我们在边权存在负数的情况下得到了错误的答案.

下面有一个例题（单源最短路径的模板题）

题目描述
编程实现Dijkstra算法，求一个有向加权图中，从源点出发到其他各个顶点的最短路径。

输入
第1行第1个值表示顶点个数，第2个值表示边个数；第2行开始为边（两个顶点，边的起点和终点）及权重。

输出
顶点0到每一个顶点的最短路径长度。

样例输入

5 7
0 1 10
0 3 30
0 4 100
1 2 50
2 4 10
3 2 20
3 4 60

样例输出
0 10 50 30 60

PS:这个题目是一个模板题，但是它默认源点是0点，所以在输入的时候没有输入源点，一般的代码都是输入三个数，顶点数，边数，与源点，代码基本一样，只要改一下一点点代码就行——如果想要源点从键盘输入，那么增加一个输入，并把起点放入队列或者动态数组里面就行。

迪杰斯特拉（朴素版）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
struct node
{
   
    int to, dis;
    bool operator<(const node x) const
    {
   
        return dis > x.dis;
    }
};
vector<node> w[maxn];
int dis[maxn], vis[maxn], n;
void dijkstra()
{
   
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[0] = 0, vis[0] = 1;
    for (int i = 0; i < w[0].size(); ++i)
    {
   
        int to = w[0][i].to;
        dis[to] = w[0][i].dis;
    }
    for (int i = 1; i < n; ++i)
    {
   
        int minn = n;
        for (int j = 1; j < n; ++j)
        {
   //找到未确定的距离0最近的点
            if (!vis[j] && dis[j] < dis[minn])
                minn = j;
        }
        vis[minn] = 1;//标记被确定的点
        for (int i = 0; i < w[minn].size(); ++i)
        {
   
            int to = w[minn][i].to;//从minn点更新其他点
            if (!vis[to] && dis[to] > dis[minn] + w[minn][i].dis)//如果发现路径0->minn->to比之前到to的路径的更优，更新
                dis[to] = dis[minn] + w[minn][i].dis;
        }
    }
}
int main()
{
   
    int m, a, b, c, v, num;
    while (~scanf("%d%d", &n, &m))
    {
   
        node now;
        for (int i = 1; i <= m; ++i)
        {
   
            scanf("%d%d%d", &a, &b, &now.dis);
            now.to = b;
            w[a].push_back(now);//vector存边，（数组也可以）
            now.to = a;
            w[b].push_back(now);
        }
        dijkstra();
        for (int i = 0; i < n; ++i)
            printf("%d%c", dis[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

定义一个优先队列加结构体重载小于号，就相当于一个小根堆了，重载把大的放在前面，然后再把排好序的数据放入优先队列那么大的就在根底了，也就形成了一个小根堆

迪杰斯特拉堆优化（邻接表存图）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
struct node
{
   
    int to, dis;
    bool operator<(const node x) const
    {
   
        return dis > x.dis;
    }
};
vector<node> w[maxn];
int dis[maxn], vis[maxn], n;
void dijkstra()
{
   
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[0] = 0;
    priority_queue<node> pq;
    node now, ne;
    now.to = 0, now.dis = 0;
    pq.push(now);
    while (!pq.empty())
    {
   
        now = pq.top(), pq.pop();
        if (vis[now.to])
            continue;
        vis[now.to] = 1;
        for (int i = 0; i < w[now.to].size(); ++i)
        {
   
            int to = w[now.to][i].to;
            if (!vis[to] && dis[to] > now.dis + w[now.to][i].dis)
            {
   
                dis[to] = now.dis + w[now.to][i].dis;
                ne.dis = dis[to];
                ne.to = to;
                pq.push(ne);
            }
        }
    }
}
int main()
{
   
    int m, a, b, c, v, num;
    while (~scanf("%d%d", &n, &m))
    {
   
        node now;
        for (int i = 1; i <= m; ++i)
        {
   
            scanf("%d%d%d", &a, &b, &now.dis);
            now.to = b;
            w[a].push_back(now); //vector存边，（数组也可以）
            now.to = a;
            w[b].push_back(now);
        }
        dijkstra();
        for (int i = 0; i < n; ++i)
            printf("%d%c", dis[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

迪杰斯特拉堆优化（链式前向星存图）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
struct edge
{
   
   int to, next, w;
} e[maxn];
int head[maxn], cnt = 1, n, m, s, vis[maxn], dis[maxn];
struct node
{
   
   int w, now;
   bool operator<(const node x) const
   {
    //大根堆，大的在前
      return w > x.w;
   }
};
priority_queue<node> q;       //定义一个大根堆
void add(int u, int v, int w) //链式前向星加边
{
   
   e[cnt].to = v;
   e[cnt].w = w;
   e[cnt].next = head[u]; //存储该点的下一条边
   head[u] = cnt++;       //更新目前该点的最后一边
}
void dijkstra()
{
   
   for (int i = 0; i < n; ++i)
      dis[i] = inf;
   dis[s] = 0; //初始化
   q.push(node{
   0, 0});
   while (!q.empty()) //如果堆栈为空，那么所有点都已经更新
   {
   
      node x = q.top();
      q.pop();
      int u = x.now; //记录堆顶并将其弹出
      if (vis[u])
         continue;
      vis[u] = 1;
      for (int i = head[u]; i; i = e[i].next) //搜索堆顶所有的连边
      {
   
         int v = e[i].to;
         if (dis[v] > dis[u] + e[i].w)
         {
   
            dis[v] = dis[u] + e[i].w;  //松弛操作
            q.push((node){
   dis[v], v}); //把新遍历的到的点加入堆中
         }
      }
   }
}
int main()
{
   
   while (~scanf("%d%d", &n, &m))
   {
   
      for (int i = 1; i <= m; ++i)
      {
   
         int x, y, z;
         scanf("%d%d%d", &x, &y, &z);
         add(x, y, z);
      }
      dijkstra();
      for (int i = 0; i < n; ++i)
         printf("%d ", dis[i]);
      printf("\n");
   }
   return 0;
}

最短路——spfa（链式前向星存图）

SPFA算法由于它上限 O(NM) = O(VE)的时间复杂度,被卡掉的几率很大.在算法竞赛中,我们需要一个更稳定的算法:dijkstra.
spfa算法参考链接

#include <bits/stdc++.h>
const long long inf = 2147483647;
const int maxn = 10005;
const int maxm = 500005;
using namespace std;
int n, m, s, num_edge = 0;
int dis[maxn], vis[maxn], head[maxm];
struct Edge
{
   
    int next, to, dis;
} edge[maxm];                           //结构体表示静态邻接表
void addedge(int from, int to, int dis) //邻接表建图
{
                                          //以下是数据结构书上的标准代码，不懂翻书看解释
    edge[++num_edge].next = head[from]; //链式存储下一条出边
    edge[num_edge].to = to;             //当前节点编号
    edge[num_edge].dis = dis;           //本条边的距离
    head[from] = num_edge;              //记录下一次的出边情况
}
void spfa()
{
   
    queue<int> q; //spfa用队列，这里用了STL的标准队列
    for (int i = 0; i < n; i++)
    {
   
        dis[i] = inf; //带权图初始化
        vis[i] = 0;   //记录点i是否在队列中，同dijkstra算法中的visited数组
    }
    q.push(0);
    dis[0] = 0;
    vis[0] = 1; //第一个顶点入队，进行标记
    while (!q.empty())
    {
   
        int u = q.front(); //取出队首
        q.pop();
        vis[u] = 0;                                //出队标记
        for (int i = head[u]; i; i = edge[i].next) //邻接表遍历，不多解释了（也可用vector代替）
        {
   
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].dis) //如果有最短路就更改
            {
   
                dis[v] = dis[u] + edge[i].dis;
                if (vis[v] == 0) //未入队则入队
                {
   
                    vis[v] = 1; //标记入队
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
   
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
   
        int f, g, w;
        cin >> f >> g >> w;
        addedge(f, g, w); //建图，有向图连一次边就可以了
    }
    spfa(); //开始跑spfa
    for (int i = 0; i < n; i++)
        if (s == i)
            cout << 0 << " "; //如果是回到自己，直接输出0
        else
            cout << dis[i] << " "; //否则打印最短距离
    return 0;
} //结束