一.Dijkstra算法
如何理解Dijkstra算法
Dijkstrashi适用于权值非负的情况。
1.定义概览
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）
2.算法描述
1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2)算法步骤：
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则
3.其他
Dijkstra完全类似于prim算法生成最小生成树。
4.代码实现
int dijkstra(int n)
{//初始化v[0]到v[i]的距离for(int i=1;i<=n;i++)dis[i] = w[0][i]; vis[0]=1;//标记v[0]点for(int i = 1; i <= n; i++){//查找最近点int min = INF,k = 0;for(int j = 0; j <= n; j++)if(!vis[j] && dis[j] < min)min = dis[j],k = j;vis[k] = 1;//标记查找到的最近点//判断是直接v[0]连接v[j]短，还是经过v[k]连接v[j]更短for(int j = 1; j <= n; j++)if(!vis[j] && min+w[k][j] < dis[j])d[j] = min+w[k][j];}return dis[j];
}二.Floyed算法
floyd算法可以有负权值的边，但不能有包含负权值边组成的回路
参考网页：http://www.cnblogs.com/rain-1/p/5033505.html
Floyed算法(实际是动态规划问题)
问题：权值矩阵matrix[i][j]表示i到j的距离，如果没有路径则为无穷
求出权值矩阵中任意两点间的最短距离
分析：对于每一对定点u,v看是否存在一个点w使从u到w再到v的路径长度比已知路径短
如果有则更新从u到w的距离
1：不用状态压缩的动态规划算法：
状态定义:d[1][i][j]表示以1作为媒介时从i到j的最短距离
d[2][i][j]表示以1，2中的点作为媒介时从i到j的最短距离
……
d[n][i][j]表示以1,2， ……n中的点作为媒介时从i到j的最短距离
状态转移方程d[k][i][j] = min(d[k-1][i][j], d[k-1][i][j]+d[k-1][k][j]);
理解为把i到j的路径氛围两种情况，一种不经过k，一种经过k
2：状态压缩表示：
假设用d[i][j]表示从i到j的最短路径
由于d[i][j]在计算中重复使用，因此表示阶段的那一维被取消了
在没有计算出来新的d[i][j]的时候d[i][j]存储的实际是d[k-1][i][j]的值
因此可以省去表示阶段的那一维
状态转移方程：d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
3.代码实现
状态压缩的Ffloyed
/* 本程序中节点标号1,2，……nfloyed算法：floyed算法实际上是动态规划，对于任意两个点u,v,看是否存在一个点w，使得从u到w再到v的距离比从u直接到v的距离短d[i][j]存储从i点到j点的最短距离 */
#define M 100
#define INF 0x3f3f3f
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int mat[M][M];
int n, m;
void FloyedOrginal()
{//用k遍历所有中间节点的可能for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j]);//是否经过k
}
void Init()
{printf("请输入节点的个数\n");scanf("%d", &n);printf("请输入已知数据的组数\n");scanf("%d", &m);for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)mat[i][j] = INF;for(int i = 0; i < m; i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);mat[u][v] = mat[v][u] = w;}
}
int main()
{Init();FloyedOrginal();printf("%d", mat[1][4]);return 0;
}三.Bellman-ford算法
Bellman_ford可以计算存在负权边的情况
bellman-ford算法进行n-1次更新（一次更新是指用所有节点进行一次松弛操作）来找到到所有节点的单源最短路。bellman-ford算法和dijkstra其实有点相似，该算法能够保证每更新一次都能确定一个节点的最短路，但与dijkstra不同的是，并不知道是那个节点的最短路被确定了，只是知道比上次多确定一个，这样进行n-1次更新后所有节点的最短路都确定了（源点的距离本来就是确定的）。
现在来说明为什么每次更新都能多找到一个能确定最短路的节点：
1.将所有节点分为两类：已知最短距离的节点和剩余节点。
2.这两类节点满足这样的性质：已知最短距离的节点的最短距离值都比剩余节点的最短路值小。（这一点也和dijkstra一样）
3.有了上面两点说明，易知到剩余节点的路径一定会经过已知节点
4.而从已知节点连到剩余节点的所有边中的最小的那个边，这条边所更新后的剩余节点就一定是确定的最短距离，从而就多找到了一个能确定最短距离的节点，不用知道它到底是哪个节点。bellman-ford的一个优势是可以用来判断是否存在负环，在不存在负环的情况下，进行了n-1次所有边的更新操作后每个节点的最短距离都确定了，再用所有边去更新一次不会改变结果。而如果存在负环，最后再更新一次会改变结果。原因是之前是假定了起点的最短距离是确定的并且是最短的，而又负环的情况下这个假设不再成立。
Bellman-ford的实现代码：
#include <stdio.h>
int main()
{int dis[10],n,m,u[10],v[10],w[10];int inf=99999999;scanf("%d %d",&n,&m);//输入点数和边数for(int i=1; i<=m; i++)scanf("%d %d %d",&u[i],&v[i],&w[i]);//输入两条边和距离for(int i=1; i<=n; i++)//初始化一号顶点到其余各个顶点的路程dis[i]=inf;dis[1]=0;//初始化点1到自己的距离为0for(int k=1; k<=n-1; k++)//Bellman核心算法语句，最多运行n-1次{int check=0;for(int i=1; i<=m; i++){if(dis[v[i]] > dis[u[i]]+w[i]){dis[v[i]] = dis[u[i]]+w[i];check = 1;}}if(check == 0) break;//由于最多运行n-1次，所以一旦全部松弛完毕就直接跳出}for(int i=1; i<=n; i++)printf("%d ",dis[i]);return 0;
}Bellman_ford效率太低，spfa是对它的优化。
四：spfa算法
1.详细讲解：http://www.360doc.com/content/13/1208/22/14357424_335569176.shtml
2.SPFA 在形式上和广度(宽度)优先搜索非常类似，不同的是bfs中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进(重新入队)，于是再次用来改进其它的点，这样反复迭代下去。
void spfa(s); //求单源点s到其它各顶点的最短距离for i=1 to n do { dis[i]=∞; vis[i]=false; } //初始化每点到s的距离，不在队列dis[s]=0; //将dis[源点]设为0vis[s]=true; //源点s入队列head=0; tail=1; q[tail]=s; //源点s入队, 头尾指针赋初值while head<tail do {head+1; //队首出队v=q[head]; //队首结点vvis[v]=false; //释放对v的标记，可以重新入队for 每条边(v,i) //对于与队首v相连的每一条边if (dis[i]>dis[v]+a[v][i]) //如果不满足三角形性质dis[i] = dis[v] + a[v][i] //松弛dis[i]if (vis[i]=false) {tail+1; q[tail]=i; vis[i]=true;} //不在队列，则加入队列}