南宁网站关键词推广,wordpress 的子主题,福田网站制作,wordpress显示当前位置 代码Bellman-Flod算法
对于带有负权值的图#xff0c;我们已经不能通过Dijkstra算法进行求解了 原因#xff1a;Dijkstra每次都会找一个距源点#xff08;设为s#xff09;最近的点#xff0c;然后将该距离定为这个点到源点的最短路径#xff1b;如果一个顶点u被加入了book…Bellman-Flod算法
对于带有负权值的图我们已经不能通过Dijkstra算法进行求解了 原因Dijkstra每次都会找一个距源点设为s最近的点然后将该距离定为这个点到源点的最短路径如果一个顶点u被加入了book[i])( book[i] 1 说明这个s到u的路径权值已被记录不可再更改)但是如果存在v到u的权值为负那么s经v到u到值要更小。 例如 如果用Dijkstra跑只能得到2这个结果但实际结果应该是1才对 s—-u 2 s—-v—- 1 为解决带负权值的问题这里需要用到Bellman-Flod算法 问题描述有如下带负权值的图求从1号点到其他各点的最短路径长度 Input 5 5 2 3 2 1 2 -3 1 5 5 4 5 2 3 4 3
Output: 0 -3 -1 2 4
import java.util.Scanner;
public class minPath {static int[] u new int[10];static int[] v new int[10];static int[] w new int[10];static int[] dis new int[10];static int n, m;static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 1; i m; i) {u[i] input.nextInt();v[i] input.nextInt();w[i] input.nextInt();}for (int i 1; i n; i) {dis[i] 99999999;}dis[1] 0;bellmanFlod();for (int i 1; i n; i) {System.out.print(dis[i] );}}private static void bellmanFlod() {/*** 由离散数学的理论得出在一个n个顶点的图中任意两点之间的最短路径最多包含n-1条边* */for (int i 1; i n - 1; i) {for (int j 1; j m; j) {if (dis[v[j]] dis[u[j]] w[j]) {dis[v[j]] dis[u[j]] w[j];}}}}
}时间复杂度O(NM)
算法优化
优化版本一
优化原因在实际操作中很多时候不会进行n-1次毕竟不是每个点都会达到n-1条边的情况的因此当不在能更新之后我们就可以终止程序了即使现在还没进行到第n-1阶段。
优化方法添加一个一维数组备份来dis如果新一轮的松弛中数组没有发生变化则可以提前跳出循环。
import java.util.Scanner;public class minPath {static int[] u new int[10];static int[] v new int[10];static int[] w new int[10];static int[] dis new int[10];static int[] bak new int[10];static int n, m;static int check, flag;static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 1; i m; i) {u[i] input.nextInt();v[i] input.nextInt();w[i] input.nextInt();}for (int i 1; i n; i) {dis[i] 99999999;}dis[1] 0;bellmanFlod();if (flag 1) {System.out.println(此图含有负权回路);} else {for (int j 1; j n; j) {System.out.print(dis[j] );}}}private static void bellmanFlod() {/*** 由离散数学的理论得出在一个n个顶点的图中任意两点之间的最短路径最多包含n-1条边* */for (int i 1; i n - 1; i) {bak[i] dis[i];for (int j 1; j m; j) {if (dis[v[j]] dis[u[j]] w[j]) {dis[v[j]] dis[u[j]] w[j];}}/*** 检测dis是否还在变化* */check 0;for (int j 1; j n; j) {if (bak[i] ! dis[i]) {check 1;break;}if (check 0) {break;}}/*** 检测负权回路* 原理最短路径所包含的边做多为n-1条在进行n-1次松弛之后如果还能继续松弛成功* 那说明此图必定含有负权回路* */flag 0;for (int j 1; j m; j) {if (dis[v[i]] dis[u[i]] w[i]) {flag 1;}}}}
}优化原因因为最短路径做多有n-1条边所以Bellman-Ford算法做多有n-1个阶段。而每个阶段都要对每条边进行“松弛操作”使得“估计值”变为“确定值”。而对于本阶段来说上个阶段松弛完的结果是不会再改变的而原算法每个阶段都会重新计算浪费时间。
优化方法每次仅对最短路“估计值”变化为“确定值”的顶点的所有出边执行松弛操作可以采用队列进行优化 时间复杂度O(NM)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class minPath {static int[] u new int[8];static int[] v new int[8];static int[] w new int[8];/*** first 要比 n 的值大1* next 要比 m 的值大1* */static int[] first new int[6];static int[] next new int[8];static int[] dis new int[6];static int[] book new int[6];static int n, m;static QueueInteger queue new LinkedList();static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 1; i n; i) {dis[i] 99999999;}dis[1] 0;for (int i 1; i n; i) {first[i] -1;}for (int i 1; i m; i) {u[i] input.nextInt();v[i] input.nextInt();w[i] input.nextInt();/*** 建立邻接表的关键语句* */next[i] first[u[i]];first[u[i]] i;}queue.offer(1);book[1] 1;bellomanFlodPlus();for (int i 1; i n; i) {System.out.print(dis[i] );}}private static void bellomanFlodPlus() {while (!queue.isEmpty()) {/*** 当前的队首元素* */int k first[queue.peek()];while (k ! -1) {if (dis[v[k]] dis[u[k]] w[k]) {dis[v[k]] dis[u[k]] w[k];/*** 用数组来判断v[k]是否已经在队列中* 不使用数组进行记录的话要迭代队列十分不方便* */if(book[v[k]] 0) {queue.offer(v[k]);book[v[k]] 1;}}k next[k];}book[queue.peek()] 0;queue.remove();}}
}
