Dijkstra算法：
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）
算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。基本步骤如下：
- 将所有的顶点分为两部分：已知最短路程的顶点集合 P 和未知最短路径的顶点集合 Q。最开始，已知最短路径的顶点集合 P 中只有源点一个顶点。我们这里用一个vis[i]数组来记录哪些点在集合 P 中。例如对于某个顶点 i，如果vis[i]为 1 则表示这个顶点在集合 P 中，如果 vis [i]为 0 则表示这个顶点在集合 Q 中。
- 设置源点 s 到自己的最短路径为 0 即 dis=0。若存在源点有能直接到达的顶点 i，则把 dist[ i ]设为 e[s][i]。同时把所有其它（源点不能直接到达的）顶点的最短路径为设为 ∞。
- 在集合 Q 的所有顶点中选择一个离源点 s 最近的顶点 u（即 dist[u]最小）加入到集合 P。并考察所有以点 u 为起点的边，对每一条边进行松弛操作。例如存在一条从 u 到 v 的边，那么可以通过将边 u->v 添加到尾部来拓展一条从 s 到 v 的路径，这条路径的长度是 dist[u]+e[u][v]。如果这个值比目前已知的 dist[v]的值要小，我们可以用新值来替代当前 dist[v]中的值。
- 重复第 3 步，如果集合 Q 为空，算法结束。最终 dist 数组中的值就是源点到所有顶点的最短路径。
Floyd算法:
Floyd算法又称为插点法，理解起来也很方便，复杂度为o(n3)，如要从结点1到结点n，可以由1直通n，再逐渐向其中插入其他结点作为中转点，不断更新在插入结点后的最短路径。
代码也很简洁，四行的算法。
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
for(int k=;k<=n;k++)
e[j][k]=min(e[j][i]+e[i][k],e[j][k]);
Spfa：
SPFA的思路比较简单，网上的说法也比较统一，NOCOW和百度百科上都有。这里在网上找到讲的比较通俗易懂的：
*SPFA(Shortest Path Faster Algorithm) *是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。 算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素， 并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。 它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
SPFA 在形式上和BFS非常类似，不同的是BFS中一个点出了队列就不可能重新进入队列，但是SPFA中 一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本 身被改进，于是再次用来改进其它的点，这样反复迭代下去。
判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。
其实吧...Spfa老被卡...最好还是用dijkstra吧
HDU-3790 最短路径（模板题）
Dijkstra版：
这个算法还能利用堆和优先队列进行优化
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0X3f3f3f3f
const ll MAXN = 1e3 + ;
const ll mod = 1e9 + ;
//权值为正
int n, m;
int vis[MAXN];
int dist[MAXN];
int a[MAXN][MAXN];
void Dijkstra(int x,int y)
{
for (int i = ; i <= n; i++)
{
dist[i] = a[x][i];
vis[i] = ;
}
vis[x] = ;
int p;
for (int i = ; i <= n; i++)
{
int minn = INF;
for (int j = ; j <= n; j++)
{
if (!vis[j] && dist[j] < minn)
{
minn = dist[j];
p = j;
}
}
vis[p] = ;
for (int j = ; j <= n; j++)
if (!vis[j] && dist[p] + a[p][j] < dist[j])
dist[j] = dist[p] + a[p][j];//更新这个找到的距离最小的点所连的点的距离
}
}
int main()
{
ios::sync_with_stdio(false);
while (cin >> n >> m && n && m)
{
memset(a,INF,sizeof(a));
for (int i = ; i < m; i++)
{
int x, y, len;
cin >> x >> y >> len;
a[x][y] = len;
a[y][x] = len; //无向图
}
Dijkstra(,n);
cout << dist[n] << endl;
}
}
Dijkstra邻接矩阵版本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
const ll MAXN = 1e3 + ;
const ll MOD = 1e9 + ;
const double pi = acos(-);
struct node
{
int v, c;
node(int a = , int b = ) { v = a, c = b; }
bool operator<(const node &a) const
{
if (c == a.c)
return v < a.v;
else
return c > a.c;
}
};
struct Edge
{
int v, cost;
Edge(int _v = , int _cost = ) { v = _v, cost = _cost; }
};
vector<Edge> G[MAXN];
bool vis[MAXN];
int dist[MAXN];
//点的编号从1开始
void Dijkstra(int n, int start)
{
memset(vis, false, sizeof(vis));
for (int i = ; i <= n; i++)
dist[i] = INF;
priority_queue<node> que;
while (!que.empty())
que.pop();
dist[start] = ;
que.push(node(start, ));
node temp;
while (!que.empty())
{
temp = que.top();
que.pop();
int u = temp.v;
if (vis[u])
continue;
vis[u] = true;
for (int i = ; i < G[u].size(); i++)
{
int v = G[temp.v][i].v;
int cost = G[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost)
{
dist[v] = dist[u] + cost;
que.push(node(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w)
{
G[u].push_back(Edge(v, w));
}
void init(int n)
{
for (int i = ; i <= n; i++)
G[i].clear();
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n, m;
while (cin >> n >> m && n && m)
{
init(n);
for (int i = ; i < m; i++)
{
int x, y, len;
cin >> x >> y >> len;
addedge(x, y, len);
addedge(y, x, len);
}
Dijkstra(n, );
cout << dist[n] << endl;
}
return ;
}
Dijkstra邻接表写法
Floyd版：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0X3f3f3f3f
const ll MAXN = 1e3 + ;
const ll mod = 1e9 + ;
//可处理权值为负的情况
int n,m;
int e[MAXN][MAXN];
void floyd()
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
for(int k=;k<=n;k++)
e[j][k]=min(e[j][i]+e[i][k],e[j][k]);
}
int main()
{
while(cin>>n>>m&&n&&m)
{
memset(e,INF,sizeof(e));
for(int i=;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
e[a][b]=c;
e[b][a]=c;
}
floyd();
cout<<e[][n]<<endl;
}
return ;
}
Floyd版
Spfa:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
const ll MAXN = 1e5 + ;
const ll MOD = 1e9 + ;
const double pi = acos(-);
int dist[MAXN];
bool vis[MAXN];
int pre[MAXN]; //pre[x]记录的是起点为x的链表之首在数组p的位置（相当于头插法）
int n, m;
struct Edge
{
int to; //边的终点
int w; //边的权值
int pre; //同一个起点的上一个边在数组E里的位置
Edge(int _to = , int _w = , int _pre = ) { to = _to, w = _w, pre = _pre; }
} E[MAXN]; //边的数目
void Spfa()
{
queue<int> q;
int g, j; //起点为1， 终点为end
int start = ;
int end = n;
for (int i = ; i <= n; i++)
dist[i] = INF;
dist[start] = ;
q.push(start);
vis[start] = ;
while (!q.empty())
{
g = q.front();
q.pop();
vis[g] = ;
for (j = pre[g]; j != -; j = E[j].pre)
{
if (dist[E[j].to] > E[j].w + dist[g]) //能够进行松弛
{
dist[E[j].to] = E[j].w + dist[g];
if (!vis[E[j].to]) //该节点v不在序列中
{
vis[E[j].to] = ;
q.push(E[j].to);
}
}
}
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
while (cin >> n >> m && n + m)
{
memset(pre, -, sizeof(pre));
int id = ;
for (int i = ; i < m; i++)
{
int x, y, len;
cin >> x >> y >> len;
E[id].to = y;
E[id].w = len;
E[id].pre = pre[x];
pre[x] = id;
id++;
//双向
E[id].to = x;
E[id].w = len;
E[id].pre = pre[y];
pre[y] = id;
id++;
}
Spfa();
cout << dist[n] << endl;
}
return ;
}//未判负环(如果某个点进入队列的次数超过V次则存在负环
Spfa邻接表
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0X3f3f3f3f
const ll MAXN = 1e3 + ;
const ll mod = 1e9 + ;
int e[MAXN][MAXN]; //邻接矩阵
bool vis[MAXN]; //标记数组
int dist[MAXN]; //源点到顶点i的最短距离
int path[MAXN]; //记录最短路的路径
int enqueue_num[MAXN]; //记录入队次数
int n; //顶点数
int m; //边数
int s; //源点
bool SPFA()
{
memset(vis, , sizeof(vis));
memset(enqueue_num, , sizeof(enqueue_num));
for (int i = ; i <= n; i++)
{
dist[i] = INF;
path[i] = s;
}
queue<int> Q;
Q.push(s);
dist[s] = ;
vis[s] = ;
enqueue_num[s]++;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
vis[u] = ;
for (int v = ; v <= n; v++)
{
if (e[u][v] != INF) //u与v直接邻接
{
if (dist[u] + e[u][v] < dist[v]) //松弛操作
{
dist[v] = dist[u] + e[u][v];
path[v] = u;
if (!vis[v])
{
Q.push(v);
enqueue_num[v]++;
if (enqueue_num[v] >= n)//说明存在负环
return false;
vis[v] = ;
}
}
}
}
}
return true;
}
/* 到某点的最短path及最短path的len */
void Print()
{
for (int i = ; i <= n; i++)
{
if (i != s)
{
int p = i;
stack<int> st;
cout << "顶点 " << s << " 到顶点 " << p << " 的最短路径是： ";
while (s != p) //路径顺序是逆向的，所以先保存到栈
{
st.push(p);
p = path[p];
}
cout << s;
while (!st.empty()) //依次从栈中取出的才是正序路径
{
cout << "--" << st.top();
st.pop();
}
cout << " 最短路径长度是：" << dist[i] << endl;
}
}
}
int main()
{
while (cin >> n >> m && n && m)
{
s=;
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
e[i][j] = INF; //初始化e数组
int u, v, w;
for (int i = ; i < m; i++)
{
cin >> u >> v >> w;
e[u][v] = w;
e[v][u] = w;
}
if (SPFA())
cout<<dist[n]<<endl;
else
cout << "Sorry,it have negative circle!\n"; //存在负环
} return ;
}
Spfa邻接矩阵