shortest path

---

前言

提示：这里可以添加本文要记录的大概内容：
例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、Dijkstra(迪杰斯特拉算法)

算法特点：
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
算法的思路
Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

Template：

有向图

void dijkstra(int node)//node 距离源点最短的点，亦可是源点
{ //从node点开始更新寻找
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0 && dist[i] > dist[node] + a[node][i])
        {                                        //可以被更新的条件
            dist[i] = dist[node] + a[node][i]; //更新
        }
    }
    int Min = 0x7f7f7f7f,minn = -1;
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0 && dist[i] < Min)
        { 
            Min = dist[i];//寻找当前最短的点
            mini = i;
        }
    }
    if (mini == -1)
        return;
    vis[minn] = 1;
    dijkstra(minn);
}

无向图（vector实现邻接表法）

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct infor
{
    int b;
    int cost;
};
vector<infor> map[100050];
int vis[100050];
int dist[100050];
int n, m, k;
const long long inf = 0x7f7f7f7f;
void dijkstra(int node)
{
    for (int i = 0; i < map[node].size(); i++)
    {
        infor a = map[node][i];
        if (dist[a.b] > dist[node] + a.cost)
        {
            dist[a.b] = dist[node] + a.cost;
        }
    }
    int Min = 0x7f7f7f7f;
    int mini = -1;
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0 && dist[i] < Min)
        {
            Min = dist[i];
            mini = i;
        }
    }
    if (mini == -1)
        return;
    vis[mini] = 1;
    dijkstra(mini);
}

int main()
{
    int begin = 1;
    cin >> n >> m >> k;
    memset(vis, 0, sizeof(vis));
    memset(dist, 0x7f7f7f7f, sizeof(dist));
    for (int i = 0; i < 10009; i++)
        map[i].clear();
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        infor node; //存储邻接节点信息

        node.b = b;
        node.cost = c;
        map[a].push_back(node);
        node.b = a;
        node.cost = c;
        map[b].push_back(node);
        /*if (a < b)  //有向图
        {
            node.b = b;
            node.cost = c;
            map[a].push_back(node); 
        }
        else
        {
            node.b = a;
            node.cost = c;
            map[b].push_back(node);
        }*/
    }
    vis[begin] = 1;
    dist[begin] = 0;
    dijkstra(begin);
    for (int i = 0; i < k; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << dist[a] + dist[b] << endl;
    }
    return 0;
}

优先队列+vector+Dijkstra(无向图)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pi;
struct EDGE
{
    int to, time;
};
struct compare //对比所用
{
    bool operator()(pi a, pi b)
    {
        if (a.second==b.second)//first=地点  second=距离  先对比距离，相同再对比地点
            return a.first > b.first;
        return a.second > b.second;
    }
};

int n, m, k ;
priority_queue<pi, vector<pi>, compare> q;//first=地点  second=距离
const int N = 1e1+5;
vector<EDGE>edge[N];
int vis[N], dis[N];

void dji(int k)
{
    q.push(make_pair(k,0));
    while (q.size())
    {
        int x = q.top().first;
        q.pop();
        if (vis[x] == 1)
            continue;
        vis[x] = 1;
         for (int i = 0; i < edge[x].size(); i++)
        {
            int y = edge[x][i].to;
            if (dis[x] + edge[x][i].time < dis[y])
            {
                dis[y] = dis[x] + edge[x][i].time;
                q.push(make_pair(y, dis[y]));
            }
        }
    }
}
int main()
{
    memset(dis,0x3f3f3f3f,sizeof(dis));
    cin >>  n >>  m >> k ;//n个点m条边,k点即源点
    dis[k] = 0;
    for (int i = 1; i <= m; i++)
    {
        int x,y,w;
        cin >> x >> y >> w;
        EDGE p;
        p.to=y,p.time=w;
        edge[x].push_back(p);
        p.to=x;
        edge[y].push_back(p);
    }
    dji(k);
    cout << dis[4];
    return 0;
}

二、Bellman-Ford(贝尔曼福特)

代码如下（示例）：

三、SPFA

代码如下（示例）：

四、Floyd（弗洛伊德算法）

Floyd算法又称为插点法，是一种利用 动态规划的思想寻找给定的 加权图中多源点之间 最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年 图灵奖获得者、斯坦福大学计算机科学系教授 罗伯特·弗洛伊德命名。
Floyd算法是解决任意两点间的最短路径的一种算法
Floyd算法是一个经典的动态规划算法
Floyd算法的时间复杂度为O(N3)，空间复杂度为O(N2)

---