网站新媒体建设方案,企业网站建设策划书范文,厦门建筑人才网,大型门户网站设计Dijkstra#xff08;迪杰斯特拉#xff09;算法
采用广度优先搜索思想#xff0c;对有向赋权图寻找最短路径。 该算法对于不含负权的有向图来说#xff0c;是目前已知的最快的单源最短路径算法。 时间复杂度#xff1a;O#xff08;n^2#xff09; 基本原理#xf…Dijkstra迪杰斯特拉算法
采用广度优先搜索思想对有向赋权图寻找最短路径。 该算法对于不含负权的有向图来说是目前已知的最快的单源最短路径算法。 时间复杂度On^2 基本原理不断为为每个顶点 v 保留目前为止所找到的从s到v的最短路径 上图为戴克斯特拉算法应用示意图。 起点以左下角的红点目标是右上角的绿点中间灰色的倒L型为障碍物。蓝色空圈表示”暂定”用以搜索下一步已经填充颜色的表示探访过图中颜色以红到绿越绿表示离起点越远。所有节点都被均匀的探索。
我们以下图为例 假设以“1”为顶点出发求解到每个顶点的最短路径若可达则输出最短路径若不可达则输出无穷大32767
shortest(1, 2)2 shortest(1, 3)4 shortest(1, 4)5 注经对比第二种路径得到的权值和较小取第二种方式 shortest(1, 5)2
算法如下
void dijkstra(AdjMatrix *G)
{int i,j;int min,minid;int tmp;int vs;int prev[MAX] {0};int dist[MAX] {0};int visited[MAX]; // visited[i]1表示顶点vs到顶点i的最短路径已成功获取。// 初始化printf(请输入要查询的单源顶点);scanf(%d,vs);vs-1;for (i 0; i G-numV; i){visited[i] 0; // 顶点i的最短路径还没获取到。prev[i] 0; // 顶点i的前驱顶点为0。dist[i] G-Edge[vs][i];// 顶点i的最短路径为顶点vs到顶点i的权。}// 对顶点vs进行初始化visited[vs] 1;//将顶点vs加入最短路径对应的visited[i]置为1 dist[vs] 0;//到自己的权为0 // 遍历G.vexnum-1次每次找出一个顶点的最短路径。for (i 1; i G-numV; i){// 寻找当前最小的路径// 即在未获取最短路径的顶点中找到离vs最近的顶点(minid)。min INF;for (j 0; j G-numV; j){if (visited[j]0 dist[j]min){min dist[j];minid j;}}visited[minid] 1;// 标记顶点minid为已经获取到最短路径// 更新当前最短路径和前驱顶点// 即当已经顶点minid的最短路径之后更新未获取最短路径的顶点的最短路径和前驱顶点。for (j 0; j G-numV; j){tmp (G-Edge[minid][j]INF ? INF : (min G-Edge[minid][j]));// 防止溢出 if (visited[j] 0 (tmp dist[j]) ){dist[j] tmp;prev[j] minid;}}}// 打印dijkstra最短路径的结果printf(dijkstra(%c): \n, G-Vertices[vs]);for (i 0; i G-numV; i)printf( shortest(%c, %c)%d\n, G-Vertices[vs], G-Vertices[i], dist[i]);
}
具体代码如下
#includestdio.h
#includestdlib.h
#define MaxVertices 100 //假设包含100个顶点
#define MaxWeight 32767 //不邻接时为32767但输出时用 ∞
#define MAX 100
#define INF (~(0x131))
typedef struct{ //包含权的邻接矩阵的的定义char Vertices[MaxVertices]; //顶点信息的数组int Edge[MaxVertices][MaxVertices]; //边的权信息的数组int numV; //当前的顶点数int numE; //当前的边数
}AdjMatrix;void CreateGraph(AdjMatrix *G) //图的生成函数
{ int n,e,vi,vj,w,i,j;printf(请输入图的顶点数和边数以空格分隔);scanf(%d%d,n,e);G-numVn;G-numEe;for(i0;in;i) //图的初始化for(j0;jn;j){ if(ij)G-Edge[i][j]0;else G-Edge[i][j]32767;}for(i0;in;i)for(i0;iG-numV;i) //将顶点存入数组中{ printf(请输入第%d个顶点的信息(整型):,i1); // G-adjlist[i].vertexgetchar(); scanf( %c,G-Vertices[i]);}printf(\n);for(i0;iG-numE;i){ printf(请输入边的信息i,j,w(以空格分隔):);scanf(%d%d%d,vi,vj,w); //若为不带权值的图则w输入1//若为带权值的图则w输入对应权值G-Edge[vi-1][vj-1]w;//①//G-Edge[vj-1][vi-1]w;//②//无向图具有对称性的规律通过①②实现//有向图不具备此性质所以只需要①}
}
void DispGraph(AdjMatrix G) //输出邻接矩阵的信息
{ int i,j;printf(\n输出顶点的信息整型:\n);for(i0;iG.numV;i)printf(%8c,G.Vertices[i]);printf(\n输出邻接矩阵:\n);printf(\t);for(i0;iG.numV;i)printf(%8c,G.Vertices[i]);for(i0;iG.numV;i){ printf(\n%8d,i1);for(j0;jG.numV;j){ if(G.Edge[i][j]32767) //两点之间无连接时权值为默认的32767但输出时为了方便输出 ∞printf(%8s, ∞);elseprintf(%8d,G.Edge[i][j]);}printf(\n); }
}
void dijkstra(AdjMatrix *G)
{int i,j;int min,minid;int tmp;int vs;int prev[MAX] {0};int dist[MAX] {0};int visited[MAX]; // visited[i]1表示顶点vs到顶点i的最短路径已成功获取。// 初始化printf(请输入要查询的单源顶点);scanf(%d,vs);vs-1;for (i 0; i G-numV; i){visited[i] 0; // 顶点i的最短路径还没获取到。prev[i] 0; // 顶点i的前驱顶点为0。dist[i] G-Edge[vs][i];// 顶点i的最短路径为顶点vs到顶点i的权。}// 对顶点vs进行初始化visited[vs] 1;//将顶点vs加入最短路径对应的visited[i]置为1 dist[vs] 0;//到自己的权为0 // 遍历G.vexnum-1次每次找出一个顶点的最短路径。for (i 1; i G-numV; i){// 寻找当前最小的路径// 即在未获取最短路径的顶点中找到离vs最近的顶点(minid)。min INF;for (j 0; j G-numV; j){if (visited[j]0 dist[j]min){min dist[j];minid j;}}visited[minid] 1;// 标记顶点minid为已经获取到最短路径// 更新当前最短路径和前驱顶点// 即当已经顶点minid的最短路径之后更新未获取最短路径的顶点的最短路径和前驱顶点。for (j 0; j G-numV; j){tmp (G-Edge[minid][j]INF ? INF : (min G-Edge[minid][j]));// 防止溢出 if (visited[j] 0 (tmp dist[j]) ){dist[j] tmp;prev[j] minid;}}}// 打印dijkstra最短路径的结果printf(dijkstra(%c): \n, G-Vertices[vs]);for (i 0; i G-numV; i)printf( shortest(%c, %c)%d\n, G-Vertices[vs], G-Vertices[i], dist[i]);
}
int main()
{ AdjMatrix G;freopen(1.txt,r,stdin);CreateGraph(G);dijkstra(G);DispGraph(G);}
注该算法是在邻接矩阵的基础上完成的请参照邻接矩阵C语言
注由于测试输入数据较多程序可以采用文件输入 5 7 1 2 3 4 5 1 2 2 1 3 4 1 5 2 2 3 1 2 4 6 3 4 2 4 5 3 2
