图的概念

图：点--边

度->有向图（入度，出度）|| 无向图（度）

自环：若一条边的两个顶点为同一顶点，则此边称作自环。

路径：从任何一个点出发，随意在图上走，走出来的序列叫路径。| 简单路径（一条路径，每个点最多只能走一次）

特殊的图

1）没有环的无向图：树-->无向，连通，无环   || n个点 n-1条边

只有无向无环：很多个树-->森林

只有连通无环（有向）：(连通的DAG)/有向树

只有无向连通：。。。

2）有向图的树：外向树，内向树

外向：所有边的方向都是从根向外指

 内向：所有边的方向都是从外向根的方向指

3）树的扩展：章鱼图/基环树：环上每个点连出去的部分为一棵树 || n个点的章鱼图n条边

树变成章鱼图加一条边 || 章鱼图删掉环上一条边变成树

4）仙人掌图：边仙人掌，点仙人掌

边仙人掌：每条边最多在一个环上

点仙人掌：每个点最多在一个环上

点仙人掌一定是边仙人掌

5）DAG(Directed Acyclic Graph)：有向无环图

6）二分图

无向图

所有的点划为左边一部分，右边一部分，保证图当中所有的边都是从左边的一个点连到右边的一个点

树一定是二分图

图的储存方法

邻接矩阵   ----------      边表

优点：O(1)检查  ||  O(m)的内存

缺点：内存大，重边只能记一条  ||  检查

最短路

单源最短路问题：求一点到所有点的最短路

多源最短路问题：求多点到所有点的最短路

最短路中的三角不等式：

dis[i][k]+dis[k][j]>=dis[i][j]

松弛操作

求最短路过程中

if  dis[i][k]+k->j（k到j的长度）<dis[i][j]
{
　　dis[i][j]==dis[i][k]+k->j
}

 通过一条边来更新最短路的操作叫做松弛操作

最短路问题

1）Floyd

多源最短路算法

求任意连点之间的最短路

时间复杂度O(n³) || 空间复杂度O(n²)

处理范围n<=200~500

2）Dijkstra

单元最短路算法（前提：边权>=0）

求一个点到其他点的最短路

（1-->1的最短路是0）

3）Dijkstra+Heap

4）Bellman-Ford

5）SPFA

 1 //By:Komorebi_03
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 #define int long long
 5 const int INF = 2147483647;
 6 const int N = 1e6+5;
 7 int n,m,s,e_cnt,dis[N],vis[N],head[N];
 8 struct node{
 9     int v;
10     int w;
11     int nxt;
12 }e[N];
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
17     while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
18     return x*f;
19 }
20 
21 void add(int u,int v,int w)
22 {
23     e[++e_cnt].v=v;
24     e[e_cnt].w=w;
25     e[e_cnt].nxt=head[u];
26     head[u]=e_cnt;
27 }
28 
29 void SPFA()
30 {
31     queue<int> q;
32     for (int i=1;i<=n;i++)
33     {
34         dis[i]=INF;
35         vis[i]=0;
36     }
37     q.push(s);
38     dis[s]=0;
39     vis[s]=1;
40     while(!q.empty())
41     {
42         int u=q.front();
43         q.pop();
44         vis[u]=0;
45         for (int i=head[u];i;i=e[i].nxt)
46         {
47             int v=e[i].v;
48             if(dis[v]>dis[u]+e[i].w)
49             {
50                 dis[v]=dis[u]+e[i].w;
51                 if(vis[v]==0)
52                 {
53                     vis[v]=1;
54                     q.push(v);
55                 }
56             }
57         }
58     }
59 }
60 
61 signed main()
62 {
63     n=read();
64     m=read();
65     s=read();
66     for (int i=1;i<=m;i++)
67     {
68         int u=read();
69         int v=read();
70         int w=read();
71         add(u,v,w);
72     }
73     SPFA();
74     for (int i=1;i<=n;i++)
75     {
76         if(s==i)
77             cout<<0<<" ";
78         else
79             cout<<dis[i]<<" ";
80     }
81     return 0;
82 }