Prim & Dijkstra & Floyd 算法实现、联系与区别 && 使用Floyd算法求次短路径

2024-03-29 14:10| 来源: 网络整理| 查看: 265

Prim & Dijkstra & Floyd 算法实现、联系与区别 && 使用Floyd算法求次短路径目录

文章目录 Prim & Dijkstra & Floyd 算法实现、联系与区别 && 使用Floyd算法求次短路径目录掏心窝子基础知识算法详解一、Prim算法1、文字描述2、结构确定3、过程演示4、代码解析5、运行结果二、Dijkstra算法1、文字描述2、结构确定3、过程演示4、代码解析5、运行结果三、Floyd算法1、数据结构2、代码简析算法异同Floyd算法求次短路径 Prim & Dijkstra l & Floyd这几个算法其实帅的一批，就是数据结构课太恶心（懂的都懂），没有真正的体会到这些个算法的美丽之处，考试结束了，突然想写一篇文章把这几个算法揉到一起，算是了了自己一个未了的心愿。

掏心窝子

主要还是因为我本来想在极短的复习时间内用CSDN搞个算法速成，但是同一篇文章被不停地转载搬运，一大堆引流营销号在水文章，导致了网上搜算法解析的效率还没有自己看书高，间接导致了考试翻车。这谁能忍？只好自己写一篇大杂烩让后来者不要因为优质内容太少而跳进我跳进过的坑里

基础知识

First of all，Prim 和 Dijkstra算法都有同一个理论基础-- --MST性质，大意是 **假设有一个连通网络，所有节点组成一个集合G，对G的一个真子集U，如果一条边E是满足“一个端点在U中，另一个端点在G中但不在U中”条件的边里最短的一条，那么一定存在G的一棵最小生成树包含边E。**我的数学不好，这里就不给大家证明了。

算法详解一、Prim算法 1、文字描述

从任意一个顶点开始，首先把这个顶点加入到生成树T中，然后在所有一个端点在树中，一个端点不在树中的边里选择一条长度最短的，然后把这条边和边对应的节点加入生成树，依此类推，直到把所有的节点都加入生成树。

2、结构确定

确定有关的储存结构

struct edge { int vi, vj; // 边的起点和终点 int weight; // 权重 }; int w_matrix[n][n]; // 邻接矩阵 edge T[n - 1]; // 记录最小生成树 3、过程演示

在这里插入图片描述

4、代码解析 void prim(edge T[6]) // { int m, v, min; edge e; // 初始化边数组 for (int i = 1; i < 6; i++) { T[i - 1].vi = 1; T[i - 1].vj = i + 1; T[i - 1].weight = w_mtx[0][i]; } //求第 i + 1 条最小生成树的边 for (int i = 0; i < 5; i++) // 最小生成树一共有 6 - 1 = 5 条边 { min = INFI; //在 T[i] 到 T[n - 2]中选择权值最小的边加入最小生成树 for (int j = i; j < 5; j++) { if (T[j].weight < min) { min = T[j].weight; m = j; } } //把选出来的权值最短的边移到最前面 e = T[m]; T[m] = T[i]; T[i] = e; //此时新加入的边对应的顶点序号 v = T[i].vj; //更新边表，在上图的例子中就是把V1-Vn长度与V3-Vn的值进行比较 //这样的话，表中保存的始终就是一个端点在集合内，一个端点在集合外的边中最短的几条 int d = 0; for (int k = i + 1; k < 5; k++) { d = w_mtx[v - 1][T[k].vj - 1]; if (d < T[k].weight) { T[k].weight = d; T[k].vi = v; } } } } 5、运行结果

二、Dijkstra算法 1、文字描述

方法的基本操作是：将图的顶点集合V分成A、B两组，其中原点到A组中的顶点的最短路径已确定，B组的顶点未确定。初始时A中只有起点，随后从B中选出距离起点最近的节点加入A。此时，对边表进行更新：以新加入节点作为起点，遍历新节点到B中所有其他节点的距离，寻找与它相邻的点中路径最短的点，如后把这个点也加入集合A中，直到所有的节点都进入A中。

2、结构确定

确定有关的储存结构

struct path { int pre; // 前一个被加入A的节点 int length; // 权重 }; int w_mtx[n][n]; // 邻接矩阵 path dist[]; // 记录最小路径树 3、过程演示

在这里插入图片描述

4、代码解析

这里用了另一个更能体现Dijkstra算法区别于Prim算法的用例，这两种算法的区别我会在后面的文章中详细分析

void dijkstra(path dist[], int s) //s为原点序号 { int i, u, min; // 初始化dist数组 for(i = 0; i < 5; i++) { dist[i].length = w_mtx[s][i]; if (dist[i].length == INFI) { dist[i].pre = -1; } else { dist[i].pre = s; } } w_mtx[i][i] = 1; // 标记已经加入A的节点 //按顺序把节点加入A while (1) { u = -1; min 5、 INFI; for (i = 0; i < 5; i++) { if (w_mtx[i][i] == 0 && dist[i].length < min) { min = dist[i].length; u = i; } } if (u == -1) { // 如果所有的节点都已加入A(w_mtx[i][i]=0)， // 或者剩下的节点都不可达(dist[i].length=INFI)， // 则结束算法 cout D[i][k] + D[k][j]) // 核心代码 { D[i][j] = D[i][k] + D[k][j]; path[i][j] = path[k][j]; // 更新path } } } } } } 算法异同

找到一篇写的挺好的文章讲清楚了这个问题

省流:

Prim算法用于构建最小生成树——即树中所有边的权值之和最小。例如，构建电路板，使所有边的和花费最少。只能用于无向图。

Dijkstra算法用于构建单源点的最短路径树(MST)——即树中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是不能存在负权值(Bellman-Ford可以处理负权值)。

Floyd算法求次短路径

某个ACM大佬同学写的

#include #include #include #define ma 100000000 using namespace std; stack out; int n, adj[35][35][2], path[35][35][2]; void floyd_change() { for(int k = 1; k

【本文地址】

公司简介

联系我们