Dijkstra(迪杰特斯拉）

离散数学学过，不会就去跟着书上模拟一遍就完事儿（深度上进行操作）

使用条件

不能出现负权值路径

用邻接矩阵实现

#include <bits/stdc++.h>

using namespace std;
const int maxn=105,inf=1e9+7;
int mp[maxn][maxn];//图的邻接矩阵
int dis[maxn];//记录移动
bool vis[maxn];//标记
int n,m;//点、边

void DJ(int s){
    for(int i=1;i<=n;i++)
        dis[i]=inf;

    memset(vis,0,sizeof(vis));
    dis[s]=0;
    vis[s]=1;

    int turn=n;
    while(turn--){
        //Findmin
        int target=-1,minDis=inf;
        for(int i=1;i<=n;i++)
            if(!vis[i] && dis[i]<minDis)//找到所以可以走的边的最小权值
            {
                target = i;
                minDis = dis[i];
            }
        //合并
        vis[target] = 1;//找到最小后标记

        //Update
        for(int i=1;i<=n;i++){
            if(mp[target][i]!=inf && !vis[i])//如果存在边且没有被访问过
                dis[i] = min(dis[i],dis[target]+mp[target][i]);//该点的权值和前继点所有的权值取最小值
        }
    }
}

int main()
{
    cin>>n>>m;
    //初始化图
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
                mp[i][j]=mp[j][i]=inf;//相等部分，全局变量已自动初始化为0
    //存图
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        mp[u][v]=mp[v][u]=w;//无向图
        //mp[u][v]=w;有向图
    }

    DJ(1);
    cout<<dis[n]<<endl;
    return 0;
}

用邻接表实现(链式前向星)

#include <bits/stdc++.h>

using namespace std;

const int maxn=200005,inf=2147483647;
int head[maxn];
long long dis[maxn];
int vis[maxn];
int cnt=0;
int n,m,s;//点、边

struct edge{
    int v;
    int next;
    int weight;
}edge[maxn];

void add_edge(int u,int v,int w){
    edge[cnt].v = v;
    edge[cnt].weight = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void DJ(int s){
    for(int i=1;i<=n;i++)
	{
		dis[i]=2147483647;
	}

    memset(vis,0,sizeof(vis));
    dis[s]=0;

    int turn=n;
    while(turn--){
        //Findmin
        int target=s,minDis=inf;
        for(int i=1;i<=n;i++)
            if(!vis[i] && dis[i]<minDis)//找到所以可以走的边的最小权值
            {
                target = i;
                minDis = dis[i];
            }
        //合并
        vis[target] = 1;//找到最小后标记

        //Update
        for(int i=head[target];i!=-1;i=edge[i].next){
            if(!vis[edge[i].v])//如果没有被访问过
                if(dis[edge[i].v]>dis[target]+edge[i].weight)
                    dis[edge[i].v] = dis[target]+edge[i].weight;//该点的权值和前继点所有的权值取最小值
        }
    }
}

int main()
{
    cin>>n>>m>>s;
    //初始化图
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w);
    }
    DJ(s);
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    return 0;
}

堆优化（用优先队列实现）

关于优先队列

priority_queue<int> q;//从大到小
priority_queue<int, vector<int>, greater<int>>q;//从小到大
//自定义优先级
struct edge{
    int v;
    int weight;
    bool operator < (const edge A) const{//不能漏掉第二个const
        return weight > A.weight;
    }
};

priority_queue<edge> Q;//默认大根堆，需要重载成小根堆

关于Vector嵌套及遍历

vector<vector<int> > v;//v的每个元素都是一个整形动态数组

//for + iterator
	vector<int> v1 = {0,1,2,3,4,5,6};
    
	for(vector<int>::iterator x = v1.begin(); x != v1.end(); x++)
	{
		cout << *x <<" ";
	}
//for + auto
	vector<int> v1 = {0,1,2,3,4,5,6};
    
	for(auto x	: v1)
	{
		cout << x <<" ";
	}
//for + 下标
	vector<int> v1 = {0,1,2,3,4,5,6};
    
	for(int i = 0; i < v1.size(); i++)
	{
		cout << v1[i] <<" ";
	}

优化

#include <bits/stdc++.h>

using namespace std;

const int maxn=200005,inf=1e9+7;
int dis[maxn];
bool vis[maxn];
int n,m,s;//点、边
struct edge{
    int v;
    int weight; //在优先队列中是dis[v]的值；如果表示边，那么就是边权
    bool operator<(const node A) const
    //不能漏掉第二个const，会导致底层错误
    /*
    /// One of the @link comparison_functors comparison [email protected]
  template<typename _Tp>
    struct less : public binary_function<_Tp, _Tp, bool>
    {
      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const _Tp& __x, const _Tp& __y) const(这行是底层模板)
      { return __x < __y; }
    };
    */
    {
        return weight > A.weight;
    }
};

priority_queue<node> Q;//默认大根堆，需要重载成小根堆
vector<vector<node> > V;

void DJ(int s)
{
    //fill(dis, dis + n + 1, inf);
    for(int i=1;i<=n;i++)
	{
		dis[i]=inf;
	}
    dis[s] = 0;
    memset(vis, 0, sizeof(vis));
    Q.push({s, dis[s]});//v，dis[v]
    while (!Q.empty())
    {
        //FindMin
        node now = Q.top();
        Q.pop();
        if (vis[now.v])//如果访问过，就换下一个点
            continue;
        //合并
        vis[now.v] = 1;//找到最小后标记
        
        //Update
        for(auto x : V[now.v]){
            if(!vis[x.v] && dis[x.v] > dis[now.v]+x.weight){
                dis[x.v] = dis[now.v]+x.weight;
                Q.push({x.v,dis[x.v]});
            }
        }
    }
}

int main()
{
    cin>>n>>m>>s;
    
    //初始化图
    V.resize(n+1);
    for (int i = 1; i <= n; i++)
        V[i].clear();
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        V[u].push_back({v,w});
    }
    
    DJ(s);
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    return 0;
}