在线网站优化,企业信息查询app哪个最好,网站后台空间30g要多少钱,wordpress安全_Dijkstra算法#xff0c;用于求解图中从一个起点到其他所有节点的最短路径。解决单源最短路径问题的有效方法。
条件
有向
带权路径
时间复杂度 O#xff08;n平方#xff09;
方法步骤
1 把图上的点分为两个集合 要求的起点 和除了起点之外的点 。能直达的写上权值 不…Dijkstra算法用于求解图中从一个起点到其他所有节点的最短路径。解决单源最短路径问题的有效方法。
条件
有向
带权路径
时间复杂度 On平方
方法步骤
1 把图上的点分为两个集合 要求的起点 和除了起点之外的点 。能直达的写上权值 不能直达的写上无穷 自己到自己的距离是0
2 在除起点以外的中找权值最小的顶点这个顶点加入起点所在的集合。由于新顶点的并入可以把新顶点作为中转点再重新计算起点到所有除已经并入顶点的距离找最小的继续并入直到所有顶点并入起点所在的集合。
以下是对代码的详细解析和注释
代码解析
全局变量定义
#define N 1005 // 定义最大顶点数为1005
int n, m; // n表示顶点数m表示边数
bool str[N]; // 用于标记是否已确定最短路径
int dis[N]; // 存储从起始点到各个顶点的最短距离
int g[N][N]; // 邻接矩阵存储图的结构 N定义图中最大顶点数为1005。 n 和 m分别表示图中的顶点数和边数。 str布尔数组用于标记某个顶点是否已经确定了最短路径。 dis数组存储从起点到每个顶点的最短距离。 g邻接矩阵g[i][j] 表示从顶点 i 到顶点 j 的距离。
Dijkstra算法实现
void dijkstra() {// 初始化dis数组为一个很大的值这里选择0x3f3f3f3fmemset(dis, 0x3f3f3f3f, sizeof(dis));// 起始点到自身的距离为0dis[1] 0;for (int i 1; i n; i) {int temp -1; // 选择未确定的顶点// 寻找当前未确定的最小距离顶点for (int j 1; j n; j)if (!str[j] (temp -1 || dis[j] dis[temp]))temp j;// 更新与该顶点相邻的其他顶点的距离for (int j 1; j n; j)dis[j] min(dis[j], dis[temp] g[temp][j]);// 标记该顶点已经确定了最短路径str[temp] true;}// 输出结果for (int i 1; i n; i) {if (dis[i] 0x3f3f3f3f)cout -1 ; // 如果没有到该顶点的路径则输出-1elsecout dis[i] ; // 否则输出最短距离}
} 初始化 memset(dis, 0x3f3f3f3f, sizeof(dis));将 dis 数组初始化为一个很大的值0x3f3f3f3f表示初始时从起点到其他顶点的距离是无穷大。 dis[1] 0;将起点到自身的距离设置为0。 主循环 for (int i 1; i n; i)循环 n 次每次找到一个未确定最短路径的顶点。 int temp -1;初始化当前未确定的最短距离顶点为 -1。 for (int j 1; j n; j)遍历所有顶点找到未确定最短路径的顶点中距离最短的顶点 temp。 if (!str[j] (temp -1 || dis[j] dis[temp]))如果顶点 j 未确定最短路径且距离更短则更新 temp。 for (int j 1; j n; j)更新与顶点 temp 相邻的其他顶点的距离。 dis[j] min(dis[j], dis[temp] g[temp][j]);如果通过 temp 到达 j 的距离更短则更新 dis[j]。 str[temp] true;标记顶点 temp 已经确定了最短路径。 结果输出 遍历 dis 数组输出从起点到每个顶点的最短距离。 如果 dis[i] 仍然是 0x3f3f3f3f表示没有路径到达顶点 i输出 -1。 否则输出 dis[i]。
主函数
int main() {// 初始化邻接矩阵g为一个很大的值memset(g, 0x3f3f3f3f, sizeof(g));// 输入顶点数n和边数mcin n m;while (m--) { // 处理每一条边的输入int x, y, z;cin x y z;// 更新邻接矩阵g中的权值g[x][y] min(g[x][y], z);}// 调用dijkstra函数求解dijkstra();return 0;
} 初始化邻接矩阵 memset(g, 0x3f3f3f3f, sizeof(g));将邻接矩阵 g 初始化为一个很大的值0x3f3f3f3f表示初始时图中没有边。 输入图的边 cin n m;读取顶点数 n 和边数 m。 while (m--)循环 m 次读取每一条边的信息。 cin x y z;读取边的起点 x、终点 y 和权重 z。 g[x][y] min(g[x][y], z);更新邻接矩阵 g 中的权值如果有多条边连接同一对顶点只保留权重最小的那条边。 调用Dijkstra算法 dijkstra();调用 dijkstra 函数求解最短路径。 输出结果 dijkstra 函数会输出从起点到每个顶点的最短距离。
示例输入和输出
示例输入
5 7
1 2 4
1 3 3
2 4 2
3 2 1
3 4 5
4 5 1
2 5 7
示例输出
0 2 3 4 5
解释 顶点 1 到顶点 2 的最短距离为 21 - 3 - 2。 顶点 1 到顶点 3 的最短距离为 31 - 3。 顶点 1 到顶点 4 的最短距离为 41 - 3 - 2 - 4。 顶点 1 到顶点 5 的最短距离为 51 - 3 - 2 - 4 - 5。
关键点总结 邻接矩阵使用二维数组 g[N][N] 表示图的结构g[i][j] 表示从顶点 i 到顶点 j 的距离。 选择最短距离顶点通过遍历所有顶点找到未确定最短路径的顶点中距离最短的顶点。 更新邻接顶点的距离通过当前顶点更新其邻接顶点的距离。 标记顶点使用布尔数组 str 标记顶点是否已经确定了最短路径。 Dijkstra算法详细步骤解析
1. 初始化
在算法开始之前需要进行以下初始化操作 初始化距离数组 dis 将 dis 数组中的所有元素初始化为一个很大的值如 0x3f3f3f3f表示从起点到其他顶点的距离初始为无穷大。 将起点的距离设置为 0即 dis[start] 0。 初始化访问标记数组 str 将 str 数组中的所有元素初始化为 false表示所有顶点初始时都未被访问过。 初始化邻接矩阵 g 将邻接矩阵 g 中的所有元素初始化为一个很大的值如 0x3f3f3f3f表示初始时图中没有边。
2. 主循环
Dijkstra算法的核心是一个主循环该循环执行 n 次n 为顶点数每次找到一个未访问的最短距离顶点并更新其邻接顶点的距离。 选择未访问的最短距离顶点 遍历所有顶点找到未访问的顶点中距离最短的顶点 u。 如果所有顶点都已被访问过或者没有找到未访问的顶点则退出循环。 更新邻接顶点的距离 遍历顶点 u 的所有邻接顶点 v如果通过 u 到达 v 的距离更短则更新 dis[v]。 具体来说如果 dis[u] g[u][v] dis[v]则更新 dis[v] dis[u] g[u][v]。 标记顶点为已访问 将顶点 u 标记为已访问即 str[u] true避免重复处理。
3. 结果输出
在主循环结束后dis 数组中存储了从起点到每个顶点的最短距离。遍历 dis 数组输出结果 如果 dis[i] 仍然是初始的大值如 0x3f3f3f3f表示没有路径到达顶点 i输出 -1。 否则输出 dis[i]表示从起点到顶点 i 的最短距离。
示例执行过程
假设图的结构如下 顶点数 n 5 边数 m 7 边的权重如下 1 - 2: 4 1 - 3: 3 2 - 4: 2 3 - 2: 1 3 - 4: 5 4 - 5: 1 2 - 5: 7
初始化 dis 数组[0, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f] str 数组[false, false, false, false, false] g 邻接矩阵 [[0x3f3f3f3f, 4, 3, 0x3f3f3f3f, 0x3f3f3f3f],[0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 2, 0x3f3f3f3f],[0x3f3f3f3f, 1, 0x3f3f3f3f, 5, 0x3f3f3f3f],[0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 1],[0x3f3f3f3f, 7, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f]
]
第1次循环 选择未访问的最短距离顶点 遍历所有顶点找到未访问的顶点中距离最短的顶点 u 1起点。 更新邻接顶点的距离 遍历顶点 1 的邻接顶点 2 和 3 dis[2] min(dis[2], dis[1] g[1][2]) min(0x3f3f3f3f, 0 4) 4 dis[3] min(dis[3], dis[1] g[1][3]) min(0x3f3f3f3f, 0 3) 3 标记顶点为已访问 str[1] true
第2次循环 选择未访问的最短距离顶点 遍历所有顶点找到未访问的顶点中距离最短的顶点 u 3dis[3] 3。 更新邻接顶点的距离 遍历顶点 3 的邻接顶点 2 和 4 dis[2] min(dis[2], dis[3] g[3][2]) min(4, 3 1) 4 dis[4] min(dis[4], dis[3] g[3][4]) min(0x3f3f3f3f, 3 5) 8 标记顶点为已访问 str[3] true
第3次循环 选择未访问的最短距离顶点 遍历所有顶点找到未访问的顶点中距离最短的顶点 u 2dis[2] 4。 更新邻接顶点的距离 遍历顶点 2 的邻接顶点 4 和 5 dis[4] min(dis[4], dis[2] g[2][4]) min(8, 4 2) 6 dis[5] min(dis[5], dis[2] g[2][5]) min(0x3f3f3f3f, 4 7) 11 标记顶点为已访问 str[2] true
第4次循环 选择未访问的最短距离顶点 遍历所有顶点找到未访问的顶点中距离最短的顶点 u 4dis[4] 6。 更新邻接顶点的距离 遍历顶点 4 的邻接顶点 5 dis[5] min(dis[5], dis[4] g[4][5]) min(11, 6 1) 7 标记顶点为已访问 str[4] true
第5次循环 选择未访问的最短距离顶点 遍历所有顶点找到未访问的顶点中距离最短的顶点 u 5dis[5] 7。 更新邻接顶点的距离 顶点 5 没有邻接顶点无需更新。 标记顶点为已访问 str[5] true
结果输出
遍历 dis 数组输出从起点到每个顶点的最短距离 dis[1] 0 dis[2] 4 dis[3] 3 dis[4] 6 dis[5] 7
关键点总结 选择未访问的最短距离顶点 每次选择未访问的顶点中距离最短的顶点确保每一步都选择当前最优的顶点进行处理。 更新邻接顶点的距离 通过当前顶点更新其邻接顶点的距离确保每一步都更新到最新的最短距离。 标记顶点为已访问 避免重复处理已访问的顶点提高算法的效率。 结果输出 最终输出从起点到每个顶点的最短距离如果没有路径到达某个顶点则输出 -1
