备案 网站服务类型,网络媒体设计是做什么的,糖果网站建设策划书模板,WordPress二次元主题等级【0】README
0.1#xff09; 本文总结于 数据结构与算法分析#xff0c; 源代码均为原创#xff0c; 旨在理解 无权最短路径 的思想并用源代码加以实现#xff1b; 【1】无权最短路径相关概念#xff08;边的权值赋值为1#xff09;
1.1#xff09;概述#xff1a;下…【0】README
0.1 本文总结于 数据结构与算法分析 源代码均为原创 旨在理解 无权最短路径 的思想并用源代码加以实现 【1】无权最短路径相关概念边的权值赋值为1
1.1概述下图就是表示一个无权图G。使用某个顶点s作为输入参数 我们想要计算 从s到所有其他顶点的最短路径 1.20路径若我们选择s 为 v3此时立刻可以说出从s 到v3的最短路径是0路径 1.3算法描述
step1寻找所有与s 距离为 1 的顶点 此时我们看到 v1和v6 与s只有一边之遥step2寻找所有与s 距离为 2 的顶点 即找出所有邻接到 v1 和 v6的顶点与v1和v6 距离为1的顶点 得到v2和v4 所以v1到v2或者v4的距离为2 ……step3循环这个过程直到所有的顶点都被遍历到
Conclusion以上搜索过程称为广度优先搜索 广度优先搜索该方法按层处理顶点 距开始点最近的 那些顶点首先被赋值 而最远的那些顶点最后被赋值 这很像对树的层次遍历 【2】如何实现上述算法
2.1对于每个顶点 我们将跟踪三个信息info
I1dv栏(distance)我们把从s开始到顶点的距离放到 dv栏中开始的时候除开s所有的 顶点都是不可达到的而s的路径长为0I2pv栏(path) pv栏中的项为薄记变量 它将使我们能够显示出实际的路径I3known栏 Known中的项点被处理后置为1
2.2开始所有的顶点都不是 Known包括开始顶点。当一个顶点被标记为已知是 我们就确信不会再找到更便宜的路径因此对该顶点的处理实质上已经完成了 【3】我们使用类似于 拓扑排序的做法来提供寻找无权最短路径算法的性能
3.1算法描述在任一时刻 只存在两种类型的未知顶点他们的dv≠∞ 一些顶点的dvCurrDist 而其余的则有 dvCurrDist1 3.2使用队列把这种想法进一步精化 在迭代开始的时候 队列只含有距离为CurrDist的那些顶点。当我们添加距离为 CurrDist1的那些邻接顶点时 由于它们自队尾入队 因此这就保证了它们直到所有距离为 CurrDist 的顶点都被处理后才被处理。在距离为 CurrDist处的最后一个顶点出队并被处理之后 队列只含有距离为 CurrDist1的顶点 因此该过程将不断进行下去。 我们只需要把开始的节点放入队列中以启动这个过程即可 3.3时间复杂度 只要使用邻接表 则运行时间就是 O|E| |V| 3.4无权最短路径算法实例图如下 显然 某顶点出队后 更新其相应的known为1再查找出队顶点vertex的邻接顶点如果有的话将他们依次入队依次更新distance自增1且path路径更新为出队顶点vertex的顶点编号 【4】source code printing results
4.1download source code https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter9/p224_unweighted_shortest_path 4.2source code at a glance (for full code, please download source code following the given link above)
#include unweightedTable.h// allocate the memory for every element in unweighted table
UnweightedTable makeEmptyUnweightedTable()
{UnweightedTable element;element (UnweightedTable)malloc(sizeof(struct UnweightedTable));if(!element){Error(out of space ,from func makeEmptyUnweightedTable);return NULL;} element-known 0; // 1 refers to accessed , also 0 refers to not accessedelement-distance MaxInt;element-path -1; // index starts from 0return element;
}//allocate the memory for initializing unweighted table
UnweightedTable *initUnweightedTable(int size)
{ UnweightedTable* table;int i;table (UnweightedTable*)malloc(sizeof(UnweightedTable) * size);if(!table){Error(out of space ,from func initUnweightedTable);return NULL;}for(i 0; i size; i){table[i] makeEmptyUnweightedTable(); if(!table[i])return NULL;}return table;
} //computing the unweighted shortest path between the vertex under initIndex and other vertexs
void unweighted_shortest_path(AdjTable* adj, int size, int startVertex, Queue queue)
{ int adjVertex; UnweightedTable* table;ElementType vertex; AdjTable temp; table initUnweightedTable(size); enQueue(queue, startVertex-1); //if let start vertex equals to v3, then initIndex3 and let index2 enter the queue table[startVertex-1]-distance 0;// update the distance table[startVertex-1]-path 0;// update the path of starting vertexwhile(!isEmpty(queue)){vertex deQueue(queue); // if the queue is not empty, conducting departing queue table[vertex]-known 1; // update the vertex as accessed, also responding known 1temp adj[vertex]-next;while(temp){adjVertex temp-index; // let each adjVertex adjacent to vertex enter the queueif(table[adjVertex]-path -1) // key that judge whether corresponding elements path equals to -1 ,-1 means the element has never entered the queue{enQueue(queue, adjVertex); table[adjVertex]-distance table[vertex]-distance 1;// update the distance table[adjVertex]-path vertex; //update the path of adjVertex, also responding path evaluated as vertex}temp temp-next; } }disposeQueue(queue);//print unweighted tableprintUnweightedtable(table, size, startVertex);printf(\n\t);
} //print unweighted table
void printUnweightedtable(UnweightedTable* table, int size, int startVertex)
{int i;int path;char *str[4] {vertex,known,distance,path};printf(\n\t unweighted shortest path table are as follows:\n); printf(\n\t %6s%6s%9s%5s, str[0], str[1], str[2], str[3]); for(i0; isize; i){ if(i ! startVertex-1) printf(\n\t %-3d %3d %5d v%-3d , i1, table[i]-known, table[i]-distance, table[i]-path1);elseprintf(\n\t *%-3d %3d %5d %-3d , i1, table[i]-known, table[i]-distance, 0);}
}int main()
{ AdjTable* adj; Queue queue;int size 7;int i;int j;int column 4;int startVertex;int adjTable[7][4] {{2, 4, 0, 0},{4, 5, 0, 0},{1, 6, 0, 0},{3, 5, 6, 7},{7, 0, 0, 0},{0, 0, 0, 0},{6, 0, 0, 0}};printf(\n\n\t test for topological sorting with adjoining table \n);adj initAdjTable(size); queue initQueue(size);printf(\n\n\t the initial adjoining table is as follows:\n);for(i 0; i size; i)for(j 0; j column; j) if(adjTable[i][j]) insertAdj(adj, adjTable[i][j]-1, i); // insertAdj the adjoining table over printAdjTable(adj, size);// finding the unweighted shortest path starts // void unweighted_shortest_path(AdjTable* adj, int size, int initIndex, Queue queue)startVertex 3; // we set the vertex3 as the start vertex (but you know, whose index in array is 2)unweighted_shortest_path(adj, size, startVertex, queue);return 0;
}
4.3printing results
