朴素版迪杰斯特拉算法

适用范围:处理权值为正的最短路问题

步骤:

  • 初始化d[1]=0,其他d[n]=INT_MAX

  • s中放入已经确定最短路的点

  • 遍历,把不在s中的距离最近的点,加入到s

    • 更新所有点的距离

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 −1。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

#include<iostream>
#include<cstring>
using namespace std;

const int N=550;	//N表示点的数量
int a[N][N],d[N];	//d表示当前节点到1号点的距离
bool v[N];			//v表示当前节点是否已经确定最短路
int n,m;
    
int dijkstra()
{
    memset(d,0x3f3f3f3f,sizeof(d));	//初始化距离为无穷
    d[1]=0;		//1号点到1号点的距离为0
    for(int i=1;i<=n;i++)			//n个点进行n次遍历
    {
        int t=-1;		//作为起点
        for(int j=1;j<=n;j++)
        {
            if(!v[j]&&(t==-1||d[t]>d[j]))	//当前点没确定最短距离
            {							//且第一次遍历或距离比现在大
                t=j;	//更新距离
            }
        }
        v[t]=true;		//确定最短路
        for(int j=1;j<=n;j++)		//对于确定的最短路更新每个节点的距离
        {
            d[j]=min(d[j],d[t]+a[t][j]);
        }
    }
    
    if(d[n]==0x3f3f3f3f) return -1;			
    return d[n];
}

int main()
{

    cin>>n>>m;
    memset(a,0x3f3f3f3f,sizeof(a));
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a[x][y]=min(a[x][y],z); //防止两个点之间有多条边,只保留最小边
    }
    
    cout<<dijkstra();
}

堆优化版迪杰斯特拉算法

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 −1。

数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0,且不超过 10000。
数据保证:如果最短路存在,则最短路的长度不超过 109。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;

typedef pair<int, int> PII;
priority_queue<PII,vector<PII>,greater<PII>> q;
const int N = 900010;
int head[N],w[N],nxt[N],to[N],i=0;
int d[N],v[N],n,m;

void add(int a,int b,int c)
{
    to[i]=b;
    w[i]=c;
    nxt[i]=head[a];
    head[a]=i++;
}

int dijkstra()
{
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    q.push({0,1});	//第一个是距离,第二个是下标,顺序不能颠倒,根据距离排序
    while(!q.empty())
    {
        auto t=q.top();
        q.pop();
        int idx=t.second,dd=t.first;
        if(v[idx]) continue;
        v[idx]=true;
        for(int i=head[idx];i!=-1;i=nxt[i])
        {
            int j=to[i];
            if(d[j]>dd+w[i])
            {
                d[j]=dd+w[i];
                q.push({d[j],j});
            }
        }
    }
    if(d[n]>0x3f3f3f3f/2) return -1;
    return d[n];
    
}
int main()
{
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    
    cout<<dijkstra();
    
}

Q.E.D.