Dijkstra算法邻接矩阵C++及多种变换

本文共547个字,预计阅读时间需要2分钟。

定义概览

Dijkstra算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。

问题描述:在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短路径。(单源最短路径)。

原理及详解

迪杰斯特拉算法原理Dijkstra

基于邻接矩阵的C++代码

普通Dijkstra代码

在求最短路径的同时,求出最短路径的个数,并求得最短路径上的总价值(使用大于号)或者花费(使用小于号)

完整代码

注意代码中有两个Dijkstra代码,第一个是普通的Dijkstra代码,第二个是求有多少个最短路径,最短路径上增加价值或花费。

Acknowledgement

感谢柳婼提供的思路

读者评分
[评分人数: 1 平均分: 5]

评论