一个图含有\(n\)个点，\(m\)条边。其中每条边连接两个点。记所有点组成的集合为\(V\)，所有边组成的集合为\(E\)。如果图上的边有规定方向，即只能从某个点走向另外一个点，那么称整个图是有向图。如果所有的边没有方向的限制，称为无向图。一般的，在储存图的时候，需要指明方向，对于无向图而言，直接当作有两个有向边即可。
常见的储存方式有两种，一种是邻接矩阵，一种是邻接表。邻接矩阵的储存方式就是对于一条边，如果他是从\(u\)走向\(v\)长度为\(w\)，那么就直接记\(d[u][v] = w\)即以二维数组的方式记录\(u\)到\(v\)的边的长度。显然如果整个图有\(n\)个点，那么整个数组的大小就是\(n^2\)。
在某些情况下，比如点数很多而边数比较少的时候，以邻接矩阵的方式储存整个图会有大量的位置上的值没有意义，即两个点之间并不直接相连的时候，权值是无意义的。那么为了避免大量的空间的浪费，可以使用邻接表的方式储存整张图，邻接表的思想就是记录每个点出发直接相连的点有哪些。在实际的实现中，以C++为例，C++的STL中有一个结构是vector，他的作用是可变长的数组，即可以直接把一个元素插入到这个序列的末尾，那么在最开始可以给所有点开一个vector，假如有某个点是\(u->v\)那么就向\(u\)位置上的vector的末尾后面插入一个元素v。代码类似如下：
vector<int> Edge[N];// N个点，给每个点开一个vector
//1 通过某个边连向了一个点 2
Edge[1].push_back(2);// push_back表示将某个元素插入这个vector的末尾
那么，这种储存方式，只能储存对应的点的标号是谁，还不能储存权值，我们不妨把上面vector里的元素类型从单个的int换成一个二元组\(pair<int,int>\)以{编号，权值}的方式就可以一并存进去了：
Vector<pii> Edge[N];
// 1通过一个权值是3的边连向了一个点 2
Edge[1].push_back({2,3});
既然我们已经解决了图的储存问题，那么现在可以回到最开始的时候提出的问题，如何求出某些情形下的“最短路”的问题。具体而言，最短路问题可以分成下面两种分别解决。
单源最短路问题指的是，固定一个起点，求从这个起点出发，走到图上任何点上的最短的距离是多少。解决这个问题有两种算法，一种是dijkstra，一种是bellman-ford及其优化spfa。
先来说dijkstra，dijkstra算法的过程是贪心的过程：首先记\(dist[i]\)表示从\(1-i\)的最短距离是多少，其次记两个点的集合S和T，其中S表示已经算完了\(dist[i]\)的点的集合，T表示不在S集合里的点。为了方便这里记起点的编号是\(1\)，那么显然有\(dist[1]=0\)，其次起点一定一开始就在集合S里了，也就是说一开始S集合就包含一个点\(1\)，T集合里包含点\(2-N\)。
在最开始的时候，我们只知道\(dist[1]=0\)，且与\(1\)直接相连的若干个点的编号，和他们之间的相连的边的权值，于是我们就可以推出来这些相连的点的\(dist[]\)的值，显然就是他们相连的边的权值。其次我们可以发现说，在这些直接相连的点中，存在某一个点\(u\)，满足他的\(dist[u]\)小于其他所有点的值，并且这个点\(u\)的\(dist[u]\)一定已经是最小的了，也就是说这个\(u\)与起点的最短距离已经求好了，\(u\)可以从T集合中删掉，并加入S集合。之后我们可以如法炮制，第二次拿这个\(u\)当作第一步时的起点，拿他去更新与他直接相连的点的距离。如此可以抽象一下我们的算法过程：
（1）找到当前\(dist[i]\)最小的一个点\(i\)，并且\(i\)不在集合S中。
（2）拿\(i\)去更新与他直接相连的\(j\)的\(dist[j]\)，也就是\(dist[j] = dist[i] + cost(i,j)\)其中\(cost(i,j)\)表示\(i\)到\(j\)的边的权值。
（3）把\(i\)从T集合中删掉，并且加入到S集合中。
我们的这个算法如果要保证正确性，那么每次第一步取出来的点\(i\)它的\(dist[i]\)必须要保证是最小的，也就是说当前的取出来的这个点\(i\)其实已经可以放到集合S里去了才可以。那么我们上面最开始介绍这个过程的时候，显然第一步，只有起点的时候是满足的，其次第二步找到的点也是满足这个性质的，那么如果说整个过程都是正确的，其实也就是要归纳证明一下每一步取出来的点都是可以直接放到S集合中去的。那么显然归纳的第一步是正确的，第二步就是假设取出来的前\(k\)个点都满足他们的\(dist[i]\)一定是最小的，要能推出来下一个取出的\(k+1\)的从起点走到他的距离也得满足是最小的，那么通过上面的算法过程我们可以知道，假如说第\(k+1\)次第一步取出来的点是\(v\)的话，那么显然\(dist[v]\)一定是某个属于前\(k\)步取出来的某个点更新过来的，就是说有某个点\(u\)他是前\(k\)步被拿出来的，并且做了一步\(dist[v] = dist[u] + cost(u,v)\)的。假如说这个\(dist[v]\)并不是最小的，也就是违反了我们的规律的话，那么他一定是经过了某个不属于前\(k\)步取出来的点\(g\)算出来的，也就是有某个不属于前\(k\)步的点\(g\)，他有\(dist[v] = dist[u] + cost(u,v) > dist[g] + cost(g,v)\)也就是说从\(u\)走到\(v\)的距离比从\(g\)走到\(v\)的距离要严格大，但是根据之前所说的定义，既然\(g\)不属于前\(k\)步取出来的点，那么就一定有\(dist[u] < dist[g]\)否则\(g\)应该属于前\(k\)个取出来的点之中，很显然不可能有某个\(cost(g,v)\)满足加上\(dist[g]\)之后还能比\(dist[u]\)要小，除非他是负数，只要整个图上权都是正数，那么这个条件就一定是不满足的，也就是产生了矛盾，我们通过上面的算法过程取出来的每一个点，都一定有\(dist[v]\)是最小的。
那么既然第一步不会选择已经选择过的点，只要每个点都被取出过一次，也就说明所有点的\(dist[i]\)都已经达到了最小，自然整个算法过程也就结束了，下面给个不一定正确的代码说明：
// dist[i]表示从1走到i的最短距离，假如没有这样的路径，则记为正无穷
// st[i]表示i是否属于S集合，也就是这个点有没有被第一步拿出来
void dijkstra()
{
dist[1] = 0;
for(int i = 2;i <= n;++i) dist[i] = INF;//除了起点1之外的所有点初始的距离都是正无穷
for(int i = 1;i <= n;++i)
{
int t = -1;
for(int j = 1;j <= n;++j)
if(!st[j] && t == -1 || dist[t] > dist[j])
t = j;
if(t == -1) break;//假如说已经找不到这样的点t了就直接退出。
// 找到最小的dist对应的点t
for(auto& _ : Edge[t])
{
// 遍历从t走出去的所有的点，以及对应的边的权值
int v = _.first,w = _.second;// v表示对应的点的编号，w表示边的权值
if(dist[v] > dist[t] + w)
{
dist[v] = dist[t] + w;
}
}
st[t] = 1;// 标记上t，即把t加入到S集合中
}
//执行完毕后，dist[i]就表示从1走到i的最短距离
}
原文：https://www.cnblogs.com/HotPants/p/13996832.html