数据结构——Dijkstra算法（与最小生成树的Prim算法类似，可一起学习）
发布时间
阅读量：
阅读量
最短路径之Dijkstra算法
（一）Dijkstra算法
单源最短路径：即从图中的某一特定顶点出发，至其他所有顶点之间的最短路径；
【算法概述
1.1 初始化
采用邻接矩阵的方式存储图结构，首先进行初始化操作，其中每个顶点到自身的距离设置为0，而到其他顶点的距离则设定为无穷大。同时，将标记数组全部初始化为0，用以表示所有顶点均处于未访问状态；
void init(){
for(int i=0;i<nodeNum;i++){
for(int j=0;j<nodeNum;j++){
if(i==j)
matrix[i][j]=0;
else
matrix[i][j]=INF;
}
}
memset(visited,0,sizeof(visited));
}
1.2 Dijkstra主体
参数st用于表示源点，在本题中设定为0。
第一步：首先通过min_distance数组记录与源点0直接相连的各个顶点之间
全部评论 (0)
还没有任何评论哟~