一.迪杰斯特拉算法
首先对于最短路径来说：从vi-vj的最短路径，不用非要经过所有的顶点，只需要找到路径最短的路径即可；
那么迪杰斯特拉的算法：其实也就与最小生成树的思想类似，找到较小的，然后更新；
首先将dist（路径）长度初始化为两个点之间边的权值，而如果不能一次到达，就是INIFINITY
而迪杰斯特拉算法就是：加点，如果加上中转点之后，再判断此时的最短路径长度，如果此时i-j-k的路径长度小于i-k的，那么此时顶点vi的最短路径就修改为中转路径长度；并且最终将找到的最小路径的终点加入到集合S中，直至所有的顶点都在S中就找到了V0到所有其他顶点的最短路径；
就是判断，更新，但最中间的过程有点麻烦，条件判断也太多；像比于书中的用链表来表示集合的加点，加边，还是实验题中的利用标志数组更为容易，将标志数组变为0/1，这样就不用那么麻烦！！！
下面给出关于迪杰斯特拉算法的完整代码：
#define MAX_VERTEX_NUM 100
#define INFINITY 32768//表示极大值
typedef struct
{
int vex1;
int vex2;
int adj_weight;
}Arc;
typedef int VertexData;
typedef struct ArcNode
{
int adj;
}ArcNode;
typedef struct
{
VertexData vertex[MAX_VERTEX_NUM];
ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum, arcnum;
}AdjMatrix;
//邻接矩阵创建有向图
void CreateDN(AdjMatrix* G,int m)
{
int i; int j;
int** arr = (int**)malloc(m* sizeof(int*));
for (i = 0; i <m; i++)
{
arr[i] = (int*)malloc(m* sizeof(int));
}
for (i = 0; i < m; i++)
{
for (j = 0; j < m; j++)
{
scanf("%d", &arr[i][j]);
}
}
for (i = 0; i < m; i++)
{
for (j = 0; j <m; j++)
{
if (arr[i][j] != 0)
{
G->arcs[i][j].adj = arr[i][j];
}
else
{
G->arcs[i][j].adj = INFINITY;
}
}
}
G->vexnum = m;
for (i = 0; i <m; i++)
{
free(arr[i]);
}
free(arr);
}
void PrintAdj(AdjMatrix* G)
{
for (int i = 0; i <G->vexnum; i++)
{
for (int j = 0; j < G->vexnum; j++)
{
printf("%d ", G->arcs[i][j].adj);
}
printf("\n");
}
}
typedef int** PathMatrix;
typedef int* ShortPathTable;
//第五题
//path用于保存路径信息，dist用来表示最短路径长度，即边的权值
void ShortestPath_DIJ(AdjMatrix* G, int v0, PathMatrix P, ShortPathTable D)
{
int i = 0, j, w, v, min;
int final[MAX_VERTEX_NUM];
for (v = 0; v < G->vexnum; v++)
{
final[v] = 0;
D[v] = G->arcs[v0][v].adj;//从源点到点v的距离,
for (w = 0; w < G->vexnum; w++)
{
P[v][w] = 0;//从源点到w点的最短路径是否经过v点
//到所有点都设置为不可到达？设置空路径
}
if (D[v] < INFINITY)//那么初始化的时候，要再加一个附加条件，如果矩阵输入为0，则INFINITY
{
P[v][v0] = 1; P[v][v] = 1;//小于的话，就存在直接到达的路径
//那为什么还要经过v？为什么P？？？对于矩阵P的意义还是没理解
}//从源点到顶点v0中v是中间要经过的
}
D[v0] = 0;//v0到v0的距离为0；
final[v0] = 1;//到自身肯定已经遍历完成
//
for (i = 1; i < G->vexnum; i++)//这里只代表循环次数，i没有实际的意义
//表示剩余的n-1个节点
{
min = INFINITY;
for (w = 0; w < G->vexnum; w++)//有的可能从源点到达不了w，所以一直循环
//此时一直循环：
{
if (!final[w])//说明还没有找到从源点到w的路径
{
if (D[w] < min)
{
v = w;//此时将v更新为w（不要只注意前两行的,还有后面的
//为什么要更新为w呢？
//此时v在第一步肯定是要更新的，
//然后v就是代表除了v0以外的节点，那么此时也就是从v0到v的已经找到路径
min = D[w];
}
}
}//上述过程就是在找到剩下的节点中到达v0的最小的距离
final[v] = 1;//见上面的解释//此时就是最终的v才是最后真正访问的w
//将final[v]更新以后，他就不再参与后面的运算！就不会与min进行比较
//那么就是找出剩余的最短的路径——这就体现了按照路径长度递增的次序
for (w = 0; w < G->vexnum; w++)
{
if (!final[w] && (min + G->arcs[v][w].adj) < D[w])//说明找到了
//一个更短的路径,这个才是更新路径的判断条件
{
D[w] = min + G->arcs[v][w].adj;//更新最短路径
for (j = 0; j < G->vexnum; j++)
{
P[w][j] = P[v][j];//P有什么用？？?
}
P[w][w] = 1;//说明已经完成了所有的遍历？因为在循环中，所有的都设置为1了
}
}
}
for (i = 0; i < G->vexnum; i++)
{
if (i != v0)
{
if (D[i] < INFINITY)
{
printf("%d ", D[i]);
}
else
{
printf("-1 ");
}
}
}
}
int main()
{
AdjMatrix G;
//G = (AdjMatrix*)malloc(sizeof(AdjMatrix));
int m, n;
scanf("%d %d",&m, &n);
CreateDN(&G, m);
//PrintAdj(G);
PathMatrix p;
p = (int**)malloc(G.vexnum*sizeof(int*));
for (int i = 0; i < m; i++)
{
p[i] = (int*)calloc(G.vexnum,sizeof(int));
}
ShortPathTable D;
D = (int*)malloc(m*sizeof(int));
for (int i = 0; i <m; i++)
{
D[i] =INFINITY;
}
//别忘了把n加1；
ShortestPath_DIJ(&G, n, p, D);
return 0;
}二.弗洛伊德算法
若是求任意两个顶点之间的最短路径，就可以将每一个顶点作为源，多次调用迪杰斯特拉算法就可以找到任意两个顶点之间的最短路径，而利用弗洛伊德算法：就可以直接利用三重循环求出任意两点间的最短路径；
弗洛伊德算法最重要的就是要理解三重循环：
首先理解一下path：这个数组是存放i->j的最短路径的前驱结点，也就是距离j结点的最近的一个结点；
这时候：会有一个疑问，只存放一个前驱结点，那如何打印出路径上的所有结点呢？
有这个疑问就是没有理解三重循环的含义：假设i->j的前驱节点path[i][j]=p；
而p也是属于其他所有结点中的一个结点，那么自然也会有从i->p的最短路径，假设i->p的最短路径的前驱结点为m，那么i....m->p->j；也就是说，m也是属于从i->j的最短路径上的结点（因为单个值最小，所有的单个值的和肯定也最小，m,是保证从i->p的路径最短的点，那么m理应属于i->j的最短路径）以此类推直到找到距离i最近的前驱节点；此时也就找出了从顶点i到达任意所有其他结点的最小路径；而i->j的路径也就在这个过程中能够全部得出来！
综上所述：三层循环得本质我们就可以得到：i,j两层循环是作为二维数组的下标i,j；而表示从结点i到达结点j，而k则是可以作为前驱节点（中间结点）因为前驱节点肯定是在所有结点中间的，所以这层k的循环就代表这个意思；最终就能够找到所有的由顶点i到其他所有结点的最小路径；
而在打印路径的时候，根据上面的理解，path[i][j]只代表一个结点，那难道就只能打印一个结点吗？
根据上面的理解，我们既然可以找到i->j的前驱节点k，那么自然也能找到i->k的前驱结点，以此类推，递归下去，就能找到i->j的路上的所有其它的结点；
所以打印的过程是个递归的过程；
