总结一下两个最短路径的算法，这个博客总结的挺好，写的好的地方我直接贴过来了https://blog.csdn.net/daaikuaichuan/article/details/80586408
迪杰斯特拉
一、定义描述
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法的时间复杂度为O(N^2)，比如下图可求1号节点到其余所有节点的最短路径：
二、算法思想
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
三、上板子，方便查阅
#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;
const int MAX = 1e9;
int n, m;
int a[1005][1005];//图，记录权值
int lowcost[1005];
int vis[1005];//标记是否访问过
void dj(int s)
{for (int i = 1; i <= n; i++)//3.初始化每个点到指定点的最短路径{lowcost[i] = a[i][s];}memset(vis, 0, sizeof vis);vis[s] = 1;for (int i = 1; i < n; i++)//4.依次选出最短路径的点，总共n-1个，循环n的话也没关系{int MIN, min_index;MIN = MAX;min_index = i;for (int j = 1; j <= n; j++)//4.1找出最短路径的点以及下标{if (MIN > lowcost[j] && !vis[j]){MIN = lowcost[j];min_index = j;}}vis[min_index] = 1;for (int k = 1; k <= n; k++)//4.2更新一下每个点到指定点的最短距离if (lowcost[k] > lowcost[min_index] + a[min_index][k] && !vis[k])lowcost[k] = lowcost[min_index] + a[min_index][k];}
}int main()
{while (scanf_s("%d%d", &n, &m) == 2){for (int i = 1; i <= n; i++)//0.初始化矩阵for (int j = 1; j <= n; j++){a[i][j] = i == j ? 0 : MAX;}int x, y, val;for (int i = 0; i < m; i++)//1.构造邻接矩阵{scanf_s("%d%d%d", &x, &y, &val);a[x][y] = a[y][x] = val;}dj(1);//单源起点放入//5.到各个点的最短路径存在lowcost中for (int i = 1; i <= n; i++)printf("%d \n", lowcost[i]);}return 0;
}
弗洛伊德
一、定义描述
Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(N^3)。
二、算法思想
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释。
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
三、上板子，方便以后查阅
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int map[1000][1000];
int main()
{int k, i, j, n, m;//读入n和m，n表示顶点个数，m表示边的条数scanf_s("%d %d", &n, &m);//初始化for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)if (i == j)map[i][j] = map[i][j] = 0;elsemap[i][j] = map[i][j] = inf;int a, b, c;//读入边for (i = 1; i <= m; i++){scanf_s("%d %d %d", &a, &b, &c);map[a][b] = map[b][a] = c;//这是一个有向图}//Floyd-Warshall算法核心语句for (k = 1; k <= n; k++)for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)if (map[i][j] > map[i][k] + map[k][j])map[i][j] = map[i][k] + map[k][j];//输出最终的结果,最终二维数组中存的即使两点之间的最短距离int num1, num2;cin >> num1 >> num2;//输入查询的起点终点cout << map[num1][num2] << endl;return 0;
}