单源最短路径,顾名思义,就是从一个地点到多个地点的最短距离,生活中也比较常见,例如当你选择但你想去某地旅游的时候,是不是要分析一下,当你下火车的地点一定,要按照怎样的游玩顺序,走最短的路,游玩最多的景点。没错,这个算法就是来解决这个问题的————Dijkstra算法。

# Dijkstra算法历史

Dijkstra算法的中文名字叫做迪杰斯特拉,是由荷兰计算机科学家狄克斯特拉于1959年提出,解决从一个顶点到其余顶点最短路径的算法。

# Dijkstra算法思想

我就以邻接表来表达吧。在多个顶点选择一个源点即起始顶点,初始化每个顶点到达这个起始点距离都为无穷大,从这个起始点开始,找它的邻接点,如果两个点能够直通,就更新它们之间的距离,并且下一次,就以上一次的终点为起始点,向下寻找,如果存在更短的路径,就更新它们的距离,直到每个点到达源点之间的距离都是最短的时候结束。 关于不是直通的最短路径是怎么回事举个例子吧,例如<1,2>=31和2之间的距离是3,下面有<1,4>=1<4,2>=1通过点4将点1和点2连接起来,并且距离为2,所以就要此时就要更新<1,2>=2了。

# 题目描述

给出一个有向图,请从某一点出发到所有点的最短路径长度。

# 输入样例

第一行输入三个整数n,m,c,分别代表顶点个数,输入边的个数,起始点 第二行输入m行边,三个整数i,j,w

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

# 输出样例

只需要输出源点到各个点的距离即可,空格相隔。

0 2 4 3

# 代码如下

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f//极大值
using namespace std;
const int Max=1e5+4;//假设顶点的最大值
bool vis[Max];//标记一个点是否在操作队列中
int dis[Max];//存储各个点到达源点的最短距离
typedef struct EdgeNode
{
    int to;
    int w;
};//存储每个顶点的邻接点
vector<EdgeNode> s[Max];//顶点,下标代表起始点
void SPFA(int c){
    queue<int> q;//要进行操作的队列
    dis[c]=0;//初始化
    vis[c]=true;//在队列中
    q.push(c);
    while(!q.empty()){//如果队列不为空就执行
        int x=q.front();//获取队列头元素值
        q.pop();//弹出头元素
        for(auto it=s[x].begin();it!=s[x].end();it++){
            EdgeNode E=*it;//遍历这个顶点的邻接点
            if(dis[x]+E.w<dis[E.to]){
                dis[E.to]=dis[x]+E.w;
                if(!vis[E.to]){//如果这个终点没有被加入队列,就要加入
                    vis[E.to]=true;
                    q.push(E.to);
                }
            }
        }
        vis[x]=false;//操作完,标记已不再队列中
    }
}
void init(){//初始化
    memset(vis,false,sizeof(vis));
    memset(dis,inf,sizeof(dis));
}
int main()
{
    init();
    int n,m,c;
    cin >> n >> m >> c;//n个点,m条边,c源点
    for(int k=1;k<=m;k++){//输入m条边
        int i,j,w;
        cin >> i >> j >> w;
        EdgeNode e;
        e.to=j;
        e.w=w;
        s[i].push_back(e);
    }
    SPFA(c);
    for(int i=1;i<=n;i++){//输出源点到达各个顶点的最短距离
        cout << dis[i] << ' ';
    }
    return 0;
}