No.6.2 最短路径之Dijkstra算法--通过边实现松弛
一、简介：
Dijkstra算法：指定一个点（源点），求其到其他点的最短路径。称之为“单源最短路径”.
一维数组 dis 记录源点到其余各点的初始距离：
1.先找到一个距离源点A最近的点B，（区别于上一节的假设：求两点之间的最短距离，必须引入另外的点），因为边最小，其他边都是正数，即使引入其他点也不能使得这两点间的距离变小！
《基于这个假设，因为所有权边都为正数时，距离已知点的最近的点是可以确定的，保证了算法后续的正确性；但是，如果存在一条负权边，那么引入这条负权边时，可能会导致之前已经引入的点的最短路径不再正确，破坏了算法的假设基础！所以该算法不能有负权边，更勿论负权回路了！》
2.再引用上节的理论，将B最为引入点，查询是否可以缩短源点A到其他点的距离，更新dis；
3.再找到第二距离远的点C，重复以上更新，直到全部节点尝试完毕。
术语：
dis[i] 表示源点 1 到 i 的距离；
e[i][j] 表示 i 到 j 的初始距离，对应二维数组；
dis[i] + e[i][j] 表示源点 1 通过节点 i 到达 j 的距离；
二、完整code
int main(){
int inf=9999999; //根据边长和边数决定这个值的设定
int i,j,k,h,n,m,min; //min,h用于中间变量，临时存储 dis[] 最小值和索引下标
int a,b,c;
int e[100][100],dis[10];
int book[10]={0}; //已经确定的最短路径，不需再回首
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) // Initialize
for(j=1;j<=n;j++)
{
if(i==j) e[i][j]=0;
else e[i][j]=inf;
}
for(i=1;i<=m;i++) // Input manually
{
scanf("%d %d %d",&a,&b,&c);
e[a][b]=c;
}
for(i=1;i<=n;i++) //从1号定点开始
dis[i]=e[1][i];
book[1]=1;
for(i=1;i<=n;i++){ //虽然 i=1 已经确定了，但是为了循环的好看（代码简单），还是写上吧：每个点都要尝试
min=inf;
for(j=1;j<=n;j++){ //找到距离 i 最近的点，虽然有些点已经不需要再重复尝试，还是为了代码简单
if(book[j]==0 && dis[j]
}
}
book[k]=1; //不管你是i，还是j，都赋值给k了，所以book[k]=1总是没错的
for(h=1;h<=n;h++){ //确定好距离源点最近的点之后，再把所有边松弛一遍
if(e[k][h]
}
}
}
for(i=1;i<=n;i++)
printf("%d\t",dis[i]);
getchar();getchar();return 0;
}
算法的时间复杂度O(N*N + N) ~ O(N*N)，结合堆和稀疏图，还可以优化算法时间复杂度约为O(M+N)logN.
三、一张图，比较自然的表示方式是二维数组，有向、无向的都能清晰明白；但是二维数组无论是存储还是遍历，既浪费空间，也没能节省时间。对于计算机相关人士来说，要么时间换空间，要么空间换时间，现在居然出现这种两边都很low的东东，自然是不可接受的！
A.现在用数组模拟邻接表（不是指针链表）：u/ v/ w/ first/ next 都是一维数组，由于作者习惯从数组的1索引开始，所以数组长度 == 所表示的东东的长度 + 1
1.输入第 i 条边：u[i] 号顶点，v[i] 号顶点，w[i] 表示边长；
2.first[ u[i] ] 将输入的第 i 条边(u[i], v[i], w[i])的编号 i 存储在first数组的u[i]位置，如果有多条边的起始顶点 == u[i] ，那么first 数组中，后续编号会覆盖以前的编号，以前的编号记录到next数组里面；
next[i] ：表示输入的第 i 条边的“上一条边”的编号
所谓上一条边是指，同一个起始顶点的多条边，按照输入顺序，first中只记录最新一次输入的编号 i ,next 中记录了输入的历史编号！想象一下广度优先算法！
=》同理，如果 first[ v[i] ]，那么记录的就是同一个终止顶点的多条边！
for(i=1;i<=m;i++){
scanf("%d %d %d", &u[i], &v[i], &w[i]);
next[i] = first[ u[i] ]; // u[i] 第一次出现，next 记录原则：它的上一条边 -1；非首次出现，记录的就是前一次出现的输入编号
first[ u[i] ] =i; // first记录原则：在u[i] 位置，记录最新出现的输入编号
B.遍历：first、next记录的都是输入的边的编号，具体数据是存储在u/ v/ w 数组中
1.first[1] = 5：即u[5]=1, 输入的第5条边，起始顶点为1，终点v[5], 边长w[5]；上一条以 1 为起始顶点的边是：next[5] =3，即u[3],v[3],w[3]；此时 next 值为3 != -1，继续迭代 next[3] = 1，即u[1],v[1],w[1]... 直到 next=-1 止，退出next遍历；
2.继续first遍历...
k = first[1];
while(k!=-1){
printf("(%d %d %d)\t", u[k], v[k], w[k]);
k=next[k];
3.这种遍历是以first中的数据为准，即顶点个数n，而不是边数m。但是时间复杂度却是O(M)，遍历所有的输入边。
4.有没有注意到，first[3] == -1，那么遍历的时候就会跳过这一层循环，需要有自己的判断模块！
C.所以按照邻接表的方式，实现Dijkstra算法：
《写错了，下面的是Bellman-Ford算法，Dijkstra算法需要找到距离目标点最近点之后，再对其他边进行松弛，有兴趣的自己去实现，我太懒》
int main(){
int inf=9999999;
int i,j,k,n,m;
int dis[10];
int first[10],next[10];
int u[10],v[10],w[10];
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) first[i]=-1; //初始化，假设每个输入边的起始顶点都是唯一的
for(i=1;i<=m;i++) //邻接表的实现
{
scanf("%d %d %d",&u[i],&v[i],&w[i]);
next[i]=first[u[i]];
first[u[i]]=i;
}
for(i=2;i<=n;i++) // dis array
dis[i]=inf;
dis[1]=0;
// debug用的输出first/next array
printf("first array:");
for(i=1;i<=n;i++){
printf("%d\t",first[i]);
}
printf("\nnext array:");
for(i=1;i<=m;i++){
printf("%d\t",next[i]);
}
for(i=1;i<=n;i++){
k=first[i];
if(k==-1){ // 从上面的debug中，可以看出，这样的点真的是存在的
for(j=1;j<=m;j++){
if(dis[v[j]] > dis[u[j]]+w[j])
dis[v[j]] = dis[u[j]]+w[j];
}
continue;
}
while(k!=-1){
if(dis[v[k]] > dis[u[k]]+w[k]){
dis[v[k]] = dis[u[k]]+w[k];
}
k=next[k];
}
}
printf("\n");
for(i=1;i<=n;i++)
printf("%d\t",dis[i]);
getchar();getchar();return 0;
}