一，Dijkstra（迪杰斯特拉算法）
Dijkstra算法是求解单源最短路问题的算法。（非负权边）
Dijkstra提出，按各个顶点与源点之间路径长度的递增次序，生成源点到各个顶点的最短路径。
也就是说，先找出距离源点最近的一条路径，再参照它找出距离源点次近的一条路径，以此类推，直到从源点到其他各顶点的最短路径全部找出。
是一种贪心的思想。时间复杂度为n^2。
该算法仅适用于单源的非负权边的最短路问题。
如果存在负权边的话，就会出现错误。为什么？因为该算法是基于贪心思想的。如果存在负权会出现错误。
代码实现比较简单：
const int N=?;
const int INF=0xfffff
int map[N][N];
bool vis[N],dis[N],n;//用来区分
void Dijkstra(int s0){
memset(vis,false,sizeof(vis));
vis[s0]=true;
for(int i=1;i<=n;i++)
dis[i]=map[s0][i];
//-----------------------------
for(int i=1;i<=n;i++){
int Bfind=s0,Dis=INF
for(int j=1;j<=n;j++)
if(!vis[j]&&dis[j]<Dis){
Bfind=j;
Dis=dis[j];
}
if(Bfind==s0) break;
vis[Bfind]=true;
//-------------------------------
for(int j=1;j<=n;j++)
if(!vis[j]&&dis[j]<dis[Bfind]+map[Bfind][j]){
dis[j]=dis[Bfind]+map[Bfind][j];
}
//-------------------------------
}
printf("%d\n",dis[?]);
}
二，Bellman_ford（贝尔曼-福德算法）
Bellman_ford算法是求解一般单源最短路的算法。（可能存在负边）
算法操作就是，对图进行|V|-1次松弛操作，即可求出最短路径。
可以看出Bellman_ford的时间复杂度为|V||E|。
最重要的是理解什么是松弛操作：
理解了什么是松弛操作了，理解起来就很容易了。
为什么要进行|V|-1次松弛操作？
因为，某点到源点的距离最短，最多通过|V|-1次松弛操作可以得到。
代码很好写：
const int N=?;
const int M=?;
const int INF=0xffffff;
struct Edge{
int start,end;
int value;
}edge[M];
int n,m,dis[N],path[N];
void Bellman_ford(){
for(int i=1;i<=n;i++)
dis[i]=INF;
dis[startpoint]=0;
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
int st=edge[j].start;
int en=edge[j].end;
int va=edge[j].value;
if(dis[en]>dis[st]+va){
dis[en]=dis[st]+va;
path[en]=st;
}
}
}
}
如果存在负权回路，那么，那么就不存在最短路，以为，每次经过负权回路都会减小。
那么，怎么判断是否存在负权回路呢？如果存在负权回路，那么，在进行|V|次以后的松弛操作，还会变小。
所以，只需要在，做完松弛操作后，判断一下，再次做松弛操作时，会不会再次减小。
代码：（加到，松弛完以后）
bool Judge(){
for(int i=1;i<=m;i++){
int st=edge[j].start;
int en=edge[j].end;
int va=edge[j].value;
if(dis[en]>dis[st]+va)
return false;
}
}
打印路径：
需要注意的是，打印路径的时候。需要注意的是，记录的是前驱，而非后继，为什么呢？
因为，一个点最短路径的前驱是唯一的，而后继可能有很多。
递归打印路径，自己写出来的竟然。自己递归还需努力。
int path[N]={'-1'};
int Print_Path(int step){
if(path[step]==-1) return step;
else Print_Path(path[one]);
printf("%s%d",step==starstep?"":"->"?one);
}
今天的复习就到这里，明天继续。