注：对于无向无权图而言，最短路径就是经过边的条数，可以通过BFS求

对于无向带权图，有如下常用算法

单源最短路径算法
1.dijkstra算法---->贪心 单源最短路 O(n^2) 不能解决带负边权问题
多源最短路径算法
2.Floyd算法---->动态规划 多源最短路 o(n^3) 不能解决负边权回路

最短路径算法核心思想：用中转点找更短的路径

注：源点（即起点）

dijkstra算法
循环n-1次，每次找到一
最小并且未确定最短路径的点y，点y的最短路径就确定下来，然后用y去更新y的邻接点到源点的最短路径长度

时间复杂度：O(n^2)
注：n为点的个数

dijkstra算法:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
class Graph
{
public:
    int size1;//点的个数
    int size2;//边的个数
    int** graph;
    bool* visit;//标记点到源点的最短路径是否确定下来
    int* pre;//记录点的上一个中转点下标，源点中转点为其自身
    int* dist;//记录点到源点最小距离
public:
    Graph(int sz1, int sz2) :size1(sz1), size2(sz2)
    {
        graph = new int* [sz1];
        visit = new bool[sz1];
        pre = new int[sz1];
        dist = new int[sz1];
        if (graph == nullptr || visit == nullptr || pre == nullptr || dist == nullptr)
        {
            cout << "开辟失败" << endl;
        }
        else
        {
            for (int i = 0; i < sz1; ++i)
            {
                graph[i] = new int[sz1];
                if (graph[i] == nullptr)
                {
                    cout << "开辟失败" << endl;
                }
            }
            //初始化
            for (int i = 0; i < sz1; ++i)
            {
                for (int j = 0; j < sz1; ++j)
                {
                    if (i == j)
                    {
                        graph[i][j] = 0;
                    }
                    else
                    {
                        graph[i][j] = 999999;
                    }
                }
                visit[i] = false;
                pre[i] = -1;
                dist[i] = 999999;
            }
            //输入边
            int x(0);
            int y(0);
            int wi(0);
            for (int i = 0; i < sz2; ++i)
            {
                cin >> x >> y >> wi;
                graph[x][y] = graph[y][x] = wi;
            }
        }
    }
    void dijkstra()
    {
        //输入起点
        int x(0);
        cin >> x;
        visit[x] = true;
        pre[x] = x;
        dist[x] = 0;
        //更新邻接点
        for (int i = 0; i < size1; ++i)
        {
            dist[i] = graph[x][i];
        }
        //循环n-1次
        int min_n(999999);
        int k(0);//dist[k]最小
        for (int i = 0; i < size1 - 1; ++i)
        {
            min_n = 999999;
            for (int j = 0; j < size1; ++j)
            {
                if (visit[j] == false && dist[j] < min_n)
                {
                    k = j;
                    min_n = dist[j];
                }
            }
            //以k为中转点更新其邻接点dist
            
            //注：因为第一个k对应pre无法更新，所以单独判断
            if (i == 0)
            {
                visit[k] = true;
                pre[k] = x;
            }
            else
            {
                visit[k] = true;
            }
            for (int j = 0; j < size1; ++j)
            {
                if (visit[j] == false && dist[j] > (dist[k] + graph[k][j]))
                {
                    dist[j] = dist[k] + graph[k][j];
                    pre[j] = k;
                }
            }
        }
    }
};
int main()
{
    Graph g(9, 16);
    g.dijkstra();
    int y(0);
    //输入终点
    cin >> y;
    int p(y);
    while (g.pre[p] != p)
    {
        cout << p << ' ';
        p = g.pre[p];
    }
    cout << p << endl;
    cout << p << "到" << y << "最短路径长度为" << g.dist[y];
    return 0;
}
/*
9 16
0 8
0 1 1
0 2 5
1 2 3
1 3 7
1 4 5
2 4 1
2 5 7
3 4 2
3 6 3
4 5 3
4 6 6
4 7 9
5 7 5
6 7 2
6 8 7
7 8 4
*/

Floyd算法(DP): 1.判题 2.找状态数组 (1)不加中转点时 任意两点之间最短路径的距离是多少—–>初始状态:邻接矩阵 (2)加1个中转点时 任意两点之间最短路径的距离是多少 (3)加2个中转点时 任意两点之间最短路径的距离是多少 …… (n)加k个中转点时 任意两点之间最短路径的距离是多少 dp[k][i][j] = ans; 初始状态:dp[0][i][j] = g[i][j] 以前k个点做中转点时，i和j之间的最短路径的距离为ans 3.状态转移公式 第k个状态:dp[k][i][j] = min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])

    降维优化:二维
    dp[i][j] = ans;以前k个点做中转点时，i,j之间最短路径距离为ans

    第k个状态:dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])