wifi管理网站,ui设计网站开发,企业网站建设前言,国家重点项目建设网站文章目录 0 代码仓库1 Dijkstra算法2 Dijkstra算法的实现2.1 设置距离数组2.2 找到当前路径的最小值 curdis#xff0c;及对应的该顶点cur2.3 更新权重2.4 其他接口2.4.1 判断某个顶点的连通性2.4.2 求源点s到某个顶点的最短路径 3使用优先队列优化-Dijkstra算法3.1 设计内部类… 文章目录 0 代码仓库1 Dijkstra算法2 Dijkstra算法的实现2.1 设置距离数组2.2 找到当前路径的最小值 curdis及对应的该顶点cur2.3 更新权重2.4 其他接口2.4.1 判断某个顶点的连通性2.4.2 求源点s到某个顶点的最短路径 3使用优先队列优化-Dijkstra算法3.1 设计内部类node3.2 入队3.3 记录路径3.4 整体 4 Bellman-Ford算法4.1 松弛操作4.2 负权环4.3 算法思想4.4 进行V-1次松弛操作4.5 判断负权环4.6 整体 5 Floyed算法5.1 设置记录两点最短距离的数组并初始化两点之间的距离5.2 更新两点之间的距离 0 代码仓库 https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapter11_Min_Path 1 Dijkstra算法 2 Dijkstra算法的实现
2.1 设置距离数组
//用于存储从源点到当前节点的距离并初始化
dis new int[G.V()];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[s] 0;2.2 找到当前路径的最小值 curdis及对应的该顶点cur
int cur -1, curdis Integer.MAX_VALUE;for(int v 0; v G.V(); v )if(!visited[v] dis[v] curdis){curdis dis[v];cur v;}2.3 更新权重
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);}2.4 其他接口
2.4.1 判断某个顶点的连通性
public boolean isConnectedTo(int v){G.validateVertex(v);return visited[v];
}2.4.2 求源点s到某个顶点的最短路径
public int distTo(int v){G.validateVertex(v);return dis[v];
}3使用优先队列优化-Dijkstra算法
3.1 设计内部类node
存放节点编号和距离 private class Node implements ComparableNode{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;}}3.2 入队
PriorityQueueNode pq new PriorityQueueNode();pq.add(new Node(s, 0));这里的缺点就是更新node时候会重复添加节点相同的node但是路径值不一样。不影响最后结果。
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;}}
}3.3 记录路径
private int[] pre;更新pre数组
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 IterableInteger path(int t){ArrayListInteger 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;}3.4 整体
package Chapter11_Min_Path.Dijkstra_pq;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 ComparableNode{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()];PriorityQueueNode pq new PriorityQueueNode();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 IterableInteger path(int t){ArrayListInteger 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));}
}
4 Bellman-Ford算法
4.1 松弛操作 4.2 负权环 4.3 算法思想 4.4 进行V-1次松弛操作
// 进行V-1次松弛操作
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);pre[w] v;}
}4.5 判断负权环
// 多进行一次操作如果还有更新那么存在负权换
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;4.6 整体
package Chapter11_Min_Path.BellmanFord;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;public class BellmanFord {private WeightedGraph G;private int s;private int[] dis;private int[] pre;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;pre new int[G.V()];Arrays.fill(pre, -1);// 进行V-1次松弛操作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);pre[w] v;}}// 多进行一次操作如果还有更新那么存在负权换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];}public IterableInteger path(int t){ArrayListInteger res new ArrayListInteger();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(gw2.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();System.out.println(bf.path(3));}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.);}
}
5 Floyed算法 5.1 设置记录两点最短距离的数组并初始化两点之间的距离
private int[][] dis;初始化两点之间的距离
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);
}5.2 更新两点之间的距离
第一重循环测试两点之间经过点t是否存在更短的路径。 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];
