建立网站目录结构时应该注意哪几个方面,网站微商城的建设运营实践和思考,网站建设说课ppt,手机网站开发服务迪杰斯特拉算法#xff08;Dijkstras algorithm#xff09;是由荷兰计算机科学家艾兹格迪科斯彻#xff08;Edsger W. Dijkstra#xff09;在1956年提出的#xff0c;用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。这个算法广泛应用于网络路由、地图导航等领…迪杰斯特拉算法Dijkstras algorithm是由荷兰计算机科学家艾兹格·迪科斯彻Edsger W. Dijkstra在1956年提出的用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。这个算法广泛应用于网络路由、地图导航等领域。
算法原理
迪杰斯特拉算法的核心思想是贪心算法它维护一个未访问顶点集合每次从未访问顶点集合中选择一个距离源点最近的顶点然后更新该顶点相邻的顶点的距离。
算法步骤 初始化将源点到自身的距离设为0到所有其他顶点的距离设为无穷大∞。创建一个未访问顶点集合包含图中所有顶点。 选择顶点从未访问顶点集合中选择一个距离源点最近的顶点将其标记为已访问。 更新距离对于已选择的顶点检查其所有相邻的未访问顶点计算通过当前顶点到达这些相邻顶点的距离并更新它们到源点的距离如果新计算的距离比之前记录的距离更短。 重复重复步骤2和3直到所有顶点都被访问过。
算法特点 效率迪杰斯特拉算法的时间复杂度为 O(V2)O(V2)其中 VV 是顶点的数量。使用优先队列可以将其优化到 O((VE)logV)其中 E是边的数量。 适用性适用于边权重为非负的图。 局限性如果图中存在负权重边则迪杰斯特拉算法可能不会给出正确的结果。
代码实现
#includebits/stdc.husing namespace std;int n, m;//n为顶点数m为边数
int matrix[100][100];//邻接矩阵//初始化邻接矩阵
void init() {for (int i 0; i n; i) {for (int j 0; j n; j) {if (i j) {matrix[i][j] 0;} else {matrix[i][j] INT_MAX;}}}
}//初始化beginPoint到其他点的距离
vectorint initBeginDistance(int beginPoint) {vectorint beginDistance;for (int i 0; i n; i) {beginDistance.push_back(matrix[beginPoint][i]);}return beginDistance;
}//更新beginPoint到其他点的距离
void updateMatrix(int beginPoint, vectorint distances) {for (int i 0; i n; i) {matrix[beginPoint][i] distances[i];}
}//打印邻接矩阵
void printMatrix() {for (int i 0; i n; i) {for (int j 0; j n; j) {cout matrix[i][j] ;}cout endl;}
}int main() {cin n m;init();//初始化邻接矩阵for (int i 0; i m; i) {int x, y, dist;//x为起点y为终点distance为距离cin x y dist;matrix[x][y] dist;}vectorint already, unalready;//already为已经确定最短路径的点unalready为未确定最短路径的点for(int beginPoint 0; beginPoint n; beginPoint) {for(int i 0; i n; i) {if(i ! beginPoint) {unalready.push_back(i);} else {already.push_back(i);}}//初始化beginPoint到其他点的距离vectorint distances initBeginDistance(beginPoint);while(unalready.size() 0) {int minDistance INT_MAX, minIndex -1;//通过already中的点来更新beginPoint到unalready中的点的距离for(int j 0; j unalready.size(); j) {if(distances[unalready[j]] minDistance) {minDistance distances[unalready[j]];minIndex unalready[j];}}//将距离最小的点加入到already中并从unalready中删除,并且跟新beginPoint到其他点的距离already.push_back(minIndex);unalready.erase(remove(unalready.begin(), unalready.end(), minIndex), unalready.end());// 遍历未访问的节点for(int j 0; j unalready.size(); j) {// 如果当前节点可以到未访问节点并且未访问节点的距离大于当前节点到未访问节点的距离加上当前节点的距离if(matrix[minIndex][unalready[j]] ! INT_MAX distances[unalready[j]] distances[minIndex] matrix[minIndex][unalready[j]]) {// 更新未访问节点的距离distances[unalready[j]] distances[minIndex] matrix[minIndex][unalready[j]];}}}updateMatrix(beginPoint, distances);}printMatrix();return 0;
}//输入
// 5 11
// 0 1 8
// 0 2 32
// 1 0 12
// 1 2 16
// 1 3 15
// 2 1 29
// 2 4 13
// 3 1 21
// 3 4 7
// 4 2 27
// 4 3 19
