总结一下两个最短路径的算法，这个博客总结的挺好，写的好的地方我直接贴过来了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