做微网站必须要有公众号吗,软件商城免费下载app,个人电脑做网站服务器,广州市网络seo推广一.迪杰斯特拉算法
首先对于最短路径来说#xff1a;从vi-vj的最短路径#xff0c;不用非要经过所有的顶点#xff0c;只需要找到路径最短的路径即可#xff1b;
那么迪杰斯特拉的算法#xff1a;其实也就与最小生成树的思想类似#xff0c;找到较小的#xff0c;然后…一.迪杰斯特拉算法
首先对于最短路径来说从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的距离为0final[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加1ShortestPath_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的路上的所有其它的结点
所以打印的过程是个递归的过程
