河北省住房和城乡建设厅网站查询,大地seo,湖南土建网,小学网站建设报告文章目录 说明day381.Dijkstra 算法思路分析2.Prim 算法思路分析3.对比4.代码 说明
闵老师的文章链接#xff1a; 日撸 Java 三百行#xff08;总述#xff09;_minfanphd的博客-CSDN博客 自己也把手敲的代码放在了github上维护#xff1a;https://github.com/fulisha-ok/… 文章目录 说明day381.Dijkstra 算法思路分析2.Prim 算法思路分析3.对比4.代码 说明
闵老师的文章链接 日撸 Java 三百行总述_minfanphd的博客-CSDN博客 自己也把手敲的代码放在了github上维护https://github.com/fulisha-ok/sampledata
day38
1.Dijkstra 算法思路分析 假设以顶点0出发 10到各个顶点距离为0,1 60,2 2 0,3 ∞选取最小距离0,2 2
2加入0,2一条边看0到剩余顶点距离 0,1: 原0,1 6在加入0,2则可以借助0,20,22,1 5选取最小距离50,3原0,3 ∞在加入0,20,22,3 7选取最小距离7 比较5和7选取最小的距离5 0-1: 5
3加入0,22,1边看0到剩余顶点的距离 0,3原0,22,3 7在加入2,10,22,11,37; 选取最小距离0,22,3 7节点遍历完找到0到各点最短距离 0-3: 7
在这个过程中进一步思考
在实现这个过程中需要借助一些数组来存储数据 开始顶点到每一个顶点的最短距离需要有一个数组来存储并且在每循环一次都需要检查这个数组是否需要更新 开始顶点到某个顶点不一定是直连路径则需要存储开始顶点到某个顶点的路径则也需要一个数组来存储路径。 顶点是否已经确定为最短路径结点需要一个数组来做一个标志。
2.Prim 算法思路分析
prim算法为最小生成树过程任意选一个顶点如选0顶点
从0顶点到与之相连的结点之间距离最短的顶点图中为2
在02结点中选择距离最短的结点则为 1 节点
在012结点中选择距离最短的结点则为3节点
当结点树n 边树n-1即构建成功
3.对比
Dijkstra 算法是求单源最短路径可以算出开始顶点到其他顶点的最短路径但是如果权重有负数则dijstra并不能计算出正确的结果。而prim算法是构建最小生成树的一种策略。
Dijkstra 求单源最短路径时我们要给定一个顶点去找到其他结点的最短路径而最小生成树是任意选择一个顶点开始。
Dijkstra 算法适用于有向图而Prim更适合无向图我认为主要是有向图在两个节点来回可能权重不同
4.代码
在dijkstra中主要分为三个for循环一个大的for循环一次循环就可以确定从v0顶点到某个顶点的最短路径在大循环中的第一个循环是找出v0结点到剩余未访问结点中的最短路径第三个循环是已经确定某个顶点是最短路径去更新tempDistanceArraytempParentArray这两个数组。 public int[] dijikstra(int paraSource) {// Step 1. Initialize.int[] tempDistanceArray new int[numNodes];for (int i 0; i numNodes; i) {tempDistanceArray[i] weightMatrix.getValue(paraSource, i);}int[] tempParentArray new int[numNodes];Arrays.fill(tempParentArray, paraSource);// -1 for no parent.tempParentArray[paraSource] -1;// Visited nodes will not be considered further.boolean[] tempVisitedArray new boolean[numNodes];tempVisitedArray[paraSource] true;// Step 2. Main loops.int tempMinDistance;int tempBestNode -1;for (int i 0; i numNodes - 1; i) {// Step 2.1 Find out the best next node.tempMinDistance Integer.MAX_VALUE;for (int j 0; j numNodes; j) {// This node is visited.if (tempVisitedArray[j]) {continue;}if (tempMinDistance tempDistanceArray[j]) {tempMinDistance tempDistanceArray[j];tempBestNode j;}}tempVisitedArray[tempBestNode] true;// Step 2.2 Prepare for the next round.for (int j 0; j numNodes; j) {// This node is visited.if (tempVisitedArray[j]) {continue;}// This node cannot be reached.if (weightMatrix.getValue(tempBestNode, j) MAX_DISTANCE) {continue;}if (tempDistanceArray[j] tempDistanceArray[tempBestNode] weightMatrix.getValue(tempBestNode, j)) {// Change the distance.tempDistanceArray[j] tempDistanceArray[tempBestNode] weightMatrix.getValue(tempBestNode, j);// Change the parent.tempParentArray[j] tempBestNode;}}// For testSystem.out.println(The distance to each node: Arrays.toString(tempDistanceArray));System.out.println(The parent of each node: Arrays.toString(tempParentArray));}// Step 3. Output for debug.System.out.println(Finally);System.out.println(The distance to each node: Arrays.toString(tempDistanceArray));System.out.println(The parent of each node: Arrays.toString(tempParentArray));return tempDistanceArray;}在prim算法中与dijkstra算法最大的区别在与第三个循环中在更新tempDistanceArray是累加之前的边而在prim算法中则不需要累加只需要判断从这个已选结点出发到其他结点的距离是否需要更新
public int prim() {// Step 1. Initialize.// Any node can be the source.int tempSource 0;int[] tempDistanceArray new int[numNodes];for (int i 0; i numNodes; i) {tempDistanceArray[i] weightMatrix.getValue(tempSource, i);}int[] tempParentArray new int[numNodes];Arrays.fill(tempParentArray, tempSource);// -1 for no parent.tempParentArray[tempSource] -1;// Visited nodes will not be considered further.boolean[] tempVisitedArray new boolean[numNodes];tempVisitedArray[tempSource] true;// Step 2. Main loops.int tempMinDistance;int tempBestNode -1;for (int i 0; i numNodes - 1; i) {// Step 2.1 Find out the best next node.tempMinDistance Integer.MAX_VALUE;for (int j 0; j numNodes; j) {// This node is visited.if (tempVisitedArray[j]) {continue;}if (tempMinDistance tempDistanceArray[j]) {tempMinDistance tempDistanceArray[j];tempBestNode j;}}tempVisitedArray[tempBestNode] true;// Step 2.2 Prepare for the next round.for (int j 0; j numNodes; j) {// This node is visited.if (tempVisitedArray[j]) {continue;}// This node cannot be reached.if (weightMatrix.getValue(tempBestNode, j) MAX_DISTANCE) {continue;}// Attention: the difference from the Dijkstra algorithm.if (tempDistanceArray[j] weightMatrix.getValue(tempBestNode, j)) {// Change the distance.tempDistanceArray[j] weightMatrix.getValue(tempBestNode, j);// Change the parent.tempParentArray[j] tempBestNode;}}// For testSystem.out.println(The selected distance for each node: Arrays.toString(tempDistanceArray));System.out.println(The parent of each node: Arrays.toString(tempParentArray));}int resultCost 0;for (int i 0; i numNodes; i) {resultCost tempDistanceArray[i];}// Step 3. Output for debug.System.out.println(Finally);System.out.println(The parent of each node: Arrays.toString(tempParentArray));System.out.println(The total cost: resultCost);return resultCost;}单元测试 dijkstra算法从顶点0出发 prim算法
