算法简介
Dijkstra
Floyd
Bellman-Ford
SPFA
Dijkstra
算法简介：
能够求出从源点到其他点的最短路。
特点：利用贪心思想依照到源点距离从小到大的顺序依次算出最短路。
步骤：
1. 步骤2~3执行n-1次（因为n个顶点的最短路最多有n-1条边，每次都能求出一个顶点的最短路）
2. 从尚未求的最短路的顶点集中找出一个离源点最近的顶点，那么这个点已经求出最短路。
3. 更新与上述端点有关的边。
更详细的解释请到wikipedia或google:dijkstra算法。
帮助理解：
点击查看dijkstra求最短路Flash动画：
红点集S：已知最短路的点集
K：最新找到最短路的点，用以更新D{}
D{i}：从源点到i的当前最短路
P{i}：记录i点的前驱节点
代码：
//求st到ed的最短路，复杂度O(V^2)
int dijkstra( int st , int ed )
{
for (int i = 0;i <= n;i ++ ) D[i] = INF;
D[st] = 0;
while (st != ed)
{
hash[st]=1;
int tmp = INF;
for (int j = 1;j <= n;j ++)
{
D[j] = min( L[st][j]+D[st] , D[j] );
if ( !hash[j] && D[j] < tmp )
tmp = D[ st=j ];
}
}
return D[ed];
}
//求st到ed的最短路，堆优化+邻接表，复杂度O(E*log(V))
typedef struct { int l , v; } Edge;
typedef vector < Edge > VE;
struct Vex {
int v , dis;
friend bool operator<(Vex v1 , Vex v2) {
return v1.dis > v2.dis;
}
};
VE e[ MaxN ];
priority_queue < Vex > Q;
int dijkstra(VE *e , int n , int st , int ed)
{
int dis[ MaxN ] , i;
bool visited[ MaxN ] = { 0 };
for (i = 0;i < n;i ++) {
dis[ i ] = INF;
}
Vex now , next;
now.dis = dis[ now.v = st ] = 0;
Edge et;
while (!Q.empty()) Q.pop();
Q.push(now);
while (!Q.empty()) {
now = Q.top();Q.pop();
if (!visited[ now.v ]) {
visited[ now.v ] = true;
for (i = 0;i < e[ now.v ].size();i ++) {
et = e[ now.v ][ i ];
next.v = et.v;
if (!visited[ et.v ] && et.l + dis[ now.v ] < dis[ et.v ]) {
next.dis = dis[ next.v = et.v ] = et.l + dis[ now.v ];
Q.push(next);
}
}
}
}
return dis[ ed ];
}
Floyd
算法简介：
能够求出一张图中两两端点之间的最短路。
算法步骤：
DP{k,i,j} 表示利用前k个顶点作为跳板，从i->j的最短距离。
计算DP{k , i , j}时，分两种情况：
1. 不使用k顶点作为跳板 DP{ k-1 , i , j }
2. 使用k顶点作为跳板 DP{ k-1 , i , k } + DP{ k-1 , k , j}
两者取较小值。发现DP{k,*,*}只与DP{k-1,*,*}有关，且计算时不会有冲突。可省去一维。
点击查看其他人的解释。
代码：
//求两两顶点之间的最短路
//DP[i][j]初始值保存i->j的直接距离，注意i,j,k的顺序
for ( k = 0;k < n;k ++ ) {
for ( i = 0;i < n;i ++ ) {
for ( j = 0;j < n;j ++ ) {
DP[i][j] = min( DP[i][j] , DP[i][k]+DP[k][j] );
}
}
}
Bellman-Ford
算法简介：
求出从源点到其他各顶点的最短距离。
特点：可以判断负环。
算法步骤：
由于最短路最多只有V-1条边，只需利用所有边集松弛最短距离V-1次即可得到最短路。
判断是否存在负权环：如果再进行一次松弛，还有最短距离呗更新，则含有负权环。
点击查看其他人的解释。
代码：
void relax(Edge &e)
{
if ( dis[e.a] + e.l < dis[e.b] ) {
dis[e.b] = dis[e.a] + e.l;
pre[e.b] = e.a;
}
}
bool bellman_ford( vector<Edge> &E , int n)
{
int i , j;
for ( i = 1;i < n;i ++ ) {
for ( j = 0;j < E.size();j ++ ) {
relax(E[j]);
}
}
for ( j = 0;j < E.size();j ++ ) {
if (dis[E[j].a] + E[j].l < dis[E[j].b] )
return false;//还能松弛，说明有负环
}
return true;
}
SPFA
算法简介：
求出从源点到其他各顶点的最短距离。
特点：速度较快，可以判断负环。
算法步骤：
实质是广搜，从起点到其他点探索最短路，如果某个点的最短路径被更新，那么通过这个点也可能更新别的点。直到没有点被更新，算法结束。
点击这里看其他人的解释。
代码：
const int maxn = 1001;
typedef struct { int v , l; } Edge;
typedef vector< Edge > VE;
VE E[maxn];
int dis[maxn];
const int INF = -1;
void SPFA(VE *E , int n , int st , int *dis)
{
int i , now;
Edge nt;
bool hash[maxn] = {0};
hash[ st ] = true;
for ( i = 1;i <= n;i ++ ) dis[i] = INF;
dis[st] = 0;
queue < int > Q;
Q.push(st);
while (!Q.empty()){
now = Q.front();Q.pop();
hash[now] = false;
for (i = 0;i < E[now].size();i ++){
nt = E[now][i];
if (dis[nt.v] == INF || dis[nt.v] > dis[now] + nt.l ){
dis[nt.v] = dis[now] + nt.l;
if ( !hash[nt.v] ) {
hash[nt.v] = true;
Q.push(nt.v);
}
}
}
}
}
