一：dijkstra算法
时间复杂度，用优先级队列优化的话，O((M+N)logN)
求单源最短路径，要求所有边的权值非负。若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。
设road[i][j]表示相邻的i到j的路长
U集合存储已经求得的到源点最短路径的节点，S集合表示还没求得的节点
dis[i]表示i到源节点（设为0）的最短路径
vis[i]=1表示i节点在U集合中
刚开始dis[0]=0,vis[0]=1;dis[i]=maxn,vis[i]=0;
for 1 to N:
1:从S集合中找出dis[]最小的节点i
将i从S中移出，插入到U中，即vis[i]=1；
2：遍历所有与i相邻的节点j
若dis[i]+road[i][j]<dis[j]
则dis[j]=dis[i]+road[i][j];
3：转1
//求其它点到源点s的最短路径，用优先级队列优化 int road[maxn][maxn];//road[i][j]表示i与j的距离(这里指进过该条路的时间)
int dis[maxn];//dis[i]表示i点到源点s的最短路径大小
int vis[maxn];//vis[i]=1表示节点i已经求过到源点的单源最短路径
vector<int> link[maxn];//link[i]表示i与哪些点连接
int n,m; struct Node{
int u,dis; //u:节点 dis:到源点s的距离 bool operator<(const Node tmp) const{
return dis>tmp.dis; //优先级序列默认的是最先取出的是“最大的”。所以这里要从大到小排序
}
}; void dijkstra() {
priority_queue<Node> q;
Node tmp,a;
for(int i=;i<maxn;i++)
dis[i]=INF;
memset(vis,,sizeof(vis));
dis[s]=;
a.dis=;
a.u=s;
q.push(a);
while(!q.empty()) {
tmp=q.top();
q.pop();
int idx=tmp.u;
vis[idx]=;
for(int k=; k<link[idx].size(); k++) {
int v=link[idx][k];
if(!vis[v]) {
if(dis[idx]+road[idx][v]<dis[v]) {
dis[v]=dis[idx]+road[idx][v];
a.dis=dis[v];
a.u=v;
q.push(a);
}
}
}
}
}
二：Bellman-Ford 算法
邻接矩阵：O(V^3) 邻接表：O(VE)
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。
如果存在负权回路，算法会返回false值，表明最短路不存在。（负权回路的含义是，回路的权值和为负）
BF算法为什么要进行n-1次迭代？这是由于“两点间如果有最短路，那么每个节点最多经过一次。也就是说，这条路不超过n-1条边”。
因为如果一个节点经过了两次，那么我们走了一个圈。若这个圈的权为正，显然不划算；若是负圈，那么最短路不存在；若是零圈，去掉不影响最优值。
很多时候，得到最优值需要的迭代次数远小于V-1。因此在迭代过程中，可以加个判断，要是发现所有节点的最短路径估计值没有更新，就可以退出了。
//求源点s到各节点的最短路
bool Bellman_Ford(int s){
//初始化
for(int i=;i<n;i++){
dist[i]=INF; //i到源点s的距离
pre[i]=-; //i的前驱节点，用于输出路径
}
dist[s]=;
for(int i=;i<n;i++){ //进行n-1次迭代
for(each(u,v)∈E){ //对所有边松弛一次
if(dist[u]+w[u][v]<dist[v]){
dist[v]=dist[u]+w[u][v];
pre[v]=u;
}
}
}
//若进行n-1次迭代后，仍然存在可以更新的路径，表明有负权回路，返回false
for(each(u,v)∈E){
if(dist[u]+w[u][v]<dist[v]){
return false;
}
}
return true;
}
三：SPFA(Shortest Path Faster Algorithm)
时间复杂度：O(kE)，k一般小于等于2。但SPFA算法不稳定，即对于某些特殊的数据，k可能比较大。
是在BF的基础上，采用队列进行优化，算法大致流程是用一个队列来进行维护。 初始时将源加入队列，
每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
存在负权回路的话，就需要创建一个COUNT数组，当某点的入队次数超过V(顶点数)返回。
int vis[i]://用来标记点i是否在队列中
//计算源点s至各节点的最短路长，这里遍历采用邻接链表——链式前向星
void SPFA(int s){
queue<int> q;
int u,v;
dist[s]=;
q.push(s);
vis[s]=;
while(!q.empty()){
u=q.front();
q.pop();
vis[u]=;
//对u的所有出边的端点进行松弛操作，如果可以经过u使得源点到v的路径变短，则更新
for(int k=head[u];k!=-;k=edge[k].next){
v=edge[k].to;
if(dist[u]+w[u][v]<dist[v]){
dist[v]=dist[u]+w[u][v];
//若点v不在队列里，则加入到队列中
if(!vis[v]){
q.push(v);
vis[v]=;
}
}
}
}
}
下面给出链式前向星的模板：
//邻接链表存储——链式前向星
//head[i]：表示父亲节点i的所有指向子节点的最后一次与i连接的边的序号
//edge[k].next：表示编号为k的边的相邻的一条边的编号，这两条边是同一节点引出的
//edge[k].to：表示编号为k的边所指向的节点编号
//int head[n],tot;
//n为顶点数，m为边数 struct edge
{
int next,to;
}edge[m] void add(int x,int y)
{
edge[tot].next =head[x];
edge[tot].to = y;
head[x] = tot++;
}
//初始化
void init()
{
memset(head,-,sizeof(head))
tot = ;
} //遍历与x相邻的所有点v
for(int k = head[x];k!=-;k=edge[k].next)
{
int v = edge[k].to;
//...
}