有权图的最短路径算法

2023-11-29 02:04
文章标签 算法 路径 有权

本文主要是介绍有权图的最短路径算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

单源最短路径问题

Dijkstra算法

原理 ​

获得最短路径长度的Dijkstra代码实现

时间复杂度

算法优化

优先队列优化后的代码实现

时间复杂度

可以具体获得最短路径的Dijkstra代码实现 

Bellman-Ford算法

原理

代码实现 

Floyed算法

原理

代码实现 

单源最短路径问题

我们的起始点是固定点，从起始点出发到达其他各顶点的最短路径。

Dijkstra算法

此算法不能处理负权边，由于大量的应用不依赖负权边，所以这个算法有非常广泛的应用。

原理 

获得最短路径长度的Dijkstra代码实现

import java.util.Arrays;public class Dijkstra {private WeightedGraph G;private int s;//源点sprivate int[] dis;//整型数组表示源点s到某个顶点的距离private boolean[] visited;//找到还没确定最短距离的顶点public Dijkstra(WeightedGraph G, int s){this.G = G;G.validateVertex(s);//验证合法性this.s = s;dis = new int[G.V()];Arrays.fill(dis, Integer.MAX_VALUE);//赋初值dis[s] = 0;//赋初值为0visited = new boolean[G.V()];while(true){//循环的第一轮找到的必是源点sint cur = -1;//最小的dis值对应的顶点是谁 int curdis = Integer.MAX_VALUE;//当前找到的最小的dis值for(int v = 0; v < G.V(); v ++)if(!visited[v] && dis[v] < curdis){curdis = dis[v];cur = v;}if(cur == -1) break;//代表当前所有的顶点都访问过了，可以退出咯visited[cur] = true;//哪些顶点的dis值已经求出来了for(int w: G.adj(cur))if(!visited[w]){if(dis[cur] + G.getWeight(cur, w) < dis[w])dis[w] = dis[cur] + G.getWeight(cur, w);}}}public boolean isConnectedTo(int v){//判断顶点和源点的连通性G.validateVertex(v);return visited[v];}public int distTo(int v){//从源点s到顶点v对应的最短路径的长度G.validateVertex(v);return dis[v];}static public void main(String[] args){WeightedGraph g = new WeightedGraph("g.txt");Dijkstra dij = new Dijkstra(g, 0);for(int v = 0; v < g.V(); v ++)System.out.print(dij.distTo(v) + " ");System.out.println();}
}

时间复杂度

算法优化

我们可以用优先队列获得v这个顶点对应的dis值，不再是v这个顶点序号的最小值了。我们的优先队列取出来的是顶点的序号，但比较起来是比较的dis值。

优先队列优化后的代码实现

import java.util.Arrays;
import java.util.PriorityQueue;public class Dijkstra {private WeightedGraph G;private int s;private int[] dis;private boolean[] visited;private class Node implements Comparable<Node>{public int v, dis;public Node(int v, int dis){this.v = v;this.dis = dis;}@Overridepublic int compareTo(Node another){return dis - another.dis;}}public Dijkstra(WeightedGraph G, int s){this.G = G;G.validateVertex(s);this.s = s;dis = new int[G.V()];Arrays.fill(dis, Integer.MAX_VALUE);dis[s] = 0;visited = new boolean[G.V()];PriorityQueue<Node> pq = new PriorityQueue<Node>();pq.add(new Node(s, 0));while(!pq.isEmpty()){int cur = pq.remove().v;if(visited[cur]) continue;visited[cur] = true;for(int w: G.adj(cur))if(!visited[w]){if(dis[cur] + G.getWeight(cur, w) < dis[w]){dis[w] = dis[cur] + G.getWeight(cur, w);pq.add(new Node(w, dis[w]));}}}}public boolean isConnectedTo(int v){G.validateVertex(v);return visited[v];}public int distTo(int v){G.validateVertex(v);return dis[v];}static public void main(String[] args){WeightedGraph g = new WeightedGraph("g.txt");Dijkstra dij = new Dijkstra(g, 0);for(int v = 0; v < g.V(); v ++)System.out.print(dij.distTo(v) + " ");System.out.println();}
}

时间复杂度

可以具体获得最短路径的Dijkstra代码实现 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;public class Dijkstra {private WeightedGraph G;private int s;private int[] dis;private boolean[] visited;private int[] pre;private class Node implements Comparable<Node>{public int v, dis;public Node(int v, int dis){this.v = v;this.dis = dis;}@Overridepublic int compareTo(Node another){return dis - another.dis;}}public Dijkstra(WeightedGraph G, int s){this.G = G;G.validateVertex(s);this.s = s;dis = new int[G.V()];Arrays.fill(dis, Integer.MAX_VALUE);pre = new int[G.V()];Arrays.fill(pre, -1);dis[s] = 0;pre[s] = s;visited = new boolean[G.V()];PriorityQueue<Node> pq = new PriorityQueue<Node>();pq.add(new Node(s, 0));while(!pq.isEmpty()){int cur = pq.remove().v;if(visited[cur]) continue;visited[cur] = true;for(int w: G.adj(cur))if(!visited[w]){if(dis[cur] + G.getWeight(cur, w) < dis[w]){dis[w] = dis[cur] + G.getWeight(cur, w);pq.add(new Node(w, dis[w]));pre[w] = cur;}}}}public boolean isConnectedTo(int v){G.validateVertex(v);return visited[v];}public int distTo(int v){G.validateVertex(v);return dis[v];}public Iterable<Integer> path(int t){ArrayList<Integer> res = new ArrayList<>();if(!isConnectedTo(t)) return res;int cur = t;while(cur != s){res.add(cur);cur = pre[cur];}res.add(s);Collections.reverse(res);return res;}static public void main(String[] args){WeightedGraph g = new WeightedGraph("g.txt");Dijkstra dij = new Dijkstra(g, 0);for(int v = 0; v < g.V(); v ++)System.out.print(dij.distTo(v) + " ");System.out.println();System.out.println(dij.path(3));}
}

Bellman-Ford算法

原理

松弛操作有方向性，相当于拐个弯到达某个端点是不是比直接到达某个端点更近。此算法在有向图无向图也成立。

 

代码实现 

import java.util.Arrays;public class BellmanFord {private WeightedGraph G;private int s;private int[] dis;private boolean hasNegCycle = false;public BellmanFord(WeightedGraph G, int s){this.G = G;G.validateVertex(s);this.s = s;dis = new int[G.V()];Arrays.fill(dis, Integer.MAX_VALUE);dis[s] = 0;for(int pass = 1; pass < G.V(); pass ++){for(int v = 0; v < G.V(); v ++)for(int w: G.adj(v))if(dis[v] != Integer.MAX_VALUE &&dis[v] + G.getWeight(v, w) < dis[w])dis[w] = dis[v] + G.getWeight(v, w);}for(int v = 0; v < G.V(); v ++)for(int w : G.adj(v))if(dis[v] != Integer.MAX_VALUE &&dis[v] + G.getWeight(v, w) < dis[w])hasNegCycle = true;}public boolean hasNegativeCycle(){return hasNegCycle;}public boolean isConnectedTo(int v){G.validateVertex(v);return dis[v] != Integer.MAX_VALUE;}public int distTo(int v){G.validateVertex(v);if(hasNegCycle) throw new RuntimeException("exist negative cycle.");return dis[v];}static public void main(String[] args){WeightedGraph g = new WeightedGraph("g.txt");BellmanFord bf = new BellmanFord(g, 0);if(!bf.hasNegativeCycle()){for(int v = 0; v < g.V(); v ++)System.out.print(bf.distTo(v) + " ");System.out.println();}elseSystem.out.println("exist negative cycle.");WeightedGraph g2 = new WeightedGraph("g2.txt");BellmanFord bf2 = new BellmanFord(g2, 0);if(!bf2.hasNegativeCycle()){for(int v = 0; v < g2.V(); v ++)System.out.print(bf2.distTo(v) + " ");System.out.println();}elseSystem.out.println("exist negative cycle.");}
}

Floyed算法

原理

可以包含负权边，也可以包含负权环。 

代码实现 

import java.util.Arrays;public class Floyed {private WeightedGraph G;private int[][] dis;private boolean hasNegCycle = false;public Floyed(WeightedGraph G){this.G = G;dis = new int[G.V()][G.V()];for(int v = 0; v < G.V(); v ++)Arrays.fill(dis[v], Integer.MAX_VALUE);for(int v = 0; v < G.V(); v ++){dis[v][v] = 0;for(int w: G.adj(v))dis[v][w] = G.getWeight(v, w);}for(int t = 0; t < G.V(); t ++)for(int v = 0; v < G.V(); v ++)for(int w = 0; w < G.V(); w ++)if(dis[v][t] != Integer.MAX_VALUE && dis[t][w] != Integer.MAX_VALUE&& dis[v][t] + dis[t][w] < dis[v][w])dis[v][w] = dis[v][t] + dis[t][w];for(int v = 0; v < G.V(); v ++)if(dis[v][v] < 0)hasNegCycle = true;}public boolean hasNegativeCycle(){return hasNegCycle;}public boolean isConnectedTo(int v, int w){G.validateVertex(v);G.validateVertex(w);return dis[v][w] != Integer.MAX_VALUE;}public int distTo(int v, int w){G.validateVertex(v);G.validateVertex(w);return dis[v][w];}static public void main(String[] args){WeightedGraph g = new WeightedGraph("g.txt");Floyed floyed = new Floyed(g);if(!floyed.hasNegativeCycle()){for(int v = 0; v < g.V(); v ++){for(int w = 0; w < g.V(); w ++)System.out.print(floyed.distTo(v, w) + " ");System.out.println();}}elseSystem.out.println("exist negative cycle.");WeightedGraph g2 = new WeightedGraph("g2.txt");Floyed floyed2 = new Floyed(g2);if(!floyed2.hasNegativeCycle()){for(int v = 0; v < g.V(); v ++){for(int w = 0; w < g.V(); w ++)System.out.print(floyed2.distTo(v, w) + " ");System.out.println();}}elseSystem.out.println("exist negative cycle.");}
}

这篇关于有权图的最短路径算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/431056。

相关文章

springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
Linux修改pip和conda缓存路径的几种方法

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓
阅读更多...
Windows系统下如何查找JDK的安装路径

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》：本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK，或者在别人的电脑上，想
阅读更多...
Python中Windows和macOS文件路径格式不一致的解决方法

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1：使用 os.path 模块方法 2：使用 pathlib 模块（推荐）方法 3：统一使
阅读更多...
一文教你解决Python不支持中文路径的问题

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
MySQL9.0默认路径安装下重置root密码

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径，
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2