单源最短路径

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

# 输出样例

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

1

0 2 4 3

# 代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


#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;
}