百元做网站,网页美工设计说明书,企业系统化管理,网站开发人才培养目标简介 英文名Dijkstra 作用#xff1a;找到路中指定起点到指定终点的带权最短路径
核心步骤 1#xff09;确定起点#xff0c;终点 2#xff09;从未走过的点中选取从起点到权值最小点作为中心点 3#xff09;如果满足 起点到中心点权值 中心点到指定其他点的权值 起…简介 英文名Dijkstra 作用找到路中指定起点到指定终点的带权最短路径
核心步骤 1确定起点终点 2从未走过的点中选取从起点到权值最小点作为中心点 3如果满足 起点到中心点权值 中心点到指定其他点的权值 起点到其他点的权值 即Weight[start] [center] Weight [center] [other] Weight [start] [center] , 简言之有更短的路径就取更短的路
理论模拟 以A为起点D为终点如图所示 径, 更新记录更短权值路径 从未走过的点中选取权值最小点即A作为中心点标记A走过更新起点到B、F、G的路径 从未走过的点中选取权值最小点即B, 并且W:B-C W:A-C 12 10 oo 更新起点A到C的路径和,
即W: A- C W: A- B - C 1210 22 继续从未走过的点中选取权值最小点G, W: A - E oo W: A-G -E 148 22 , 更新W: A-E 为22 选取F, 由于W:A-F-E162 18 22 更新 W: A- E 18 , 选取E,由于W:A-E-D18422oo,则更新W: A-D 22 选取C,无可更新点 到达终点D! 最短路径为A-F-E-D ,最短路径和为22 Java代码实现 顶点
//顶点类
public class Vertex {public String Number; //顶点编号public ListVertexneighborVertexs; //邻居顶点public MapVertex,Integerweights; //与邻居节点之间的权值public Vertex(String number) {this.Number number;this.neighborVertexsnew LinkedList();this.weightsnew HashMap();}
}
边
public class Edge {public Vertex start;public Vertex end;public Integer weight;public Edge(Vertex start, Vertex end, Integer weight) {this.start start;this.end end;this.weight weight;}
}
最短路径返回结果
public class MinPathResult {public String minPathString; //将最短路径拼接成字符串形式如 A-B-Cpublic ListVertexminPathList; //将起点到终点的路径储存在List集合中public Integer minPathSum; //记录起点到终点的最短路径和public MinPathResult(ListVertex minPathList, String minPathString,Integer minPathSum) {this.minPathString minPathString;this.minPathList minPathList;this.minPathSumminPathSum;}Overridepublic String toString() {return Result{ minPathString: minPathString minPathSum:minPathSum};}
}
Dijkstra算法的实现,适用于无向图
import java.util.*;
//适用于无向图
public class DijkstraOperator {private ListVertexvertexs; //全部顶点private ListEdgeedges; //所有边private MapString,Vertexvertexs_map; //通过顶点编号找到顶点private final static Integer INFInteger.MAX_VALUE; //代表无穷大public DijkstraOperator(ListVertex vertexs, ListEdge edges) {this.vertexs vertexs;this.edges edges;this.vertexs_mapnew HashMap();//构建编号映射顶点for(Vertex v:vertexs){vertexs_map.put(v.Number,v);}//填充所有顶点的邻居以及权值for(int i0;iedges.size();i){//填充起点的邻居以及起点到终点的权值edges.get(i).start.neighborVertexs.add(edges.get(i).end);edges.get(i).start.weights.put(edges.get(i).end,edges.get(i).weight);//填充终点的邻居以及终点到起点的权值edges.get(i).end.neighborVertexs.add(edges.get(i).start);edges.get(i).end.weights.put(edges.get(i).start,edges.get(i).weight);}}//获得从起点到终点之间的路径public MinPathResult getMinPath(String start, String end){//用哈希表标记某个顶点是否走过MapVertex,Booleanvisitednew HashMap();//用哈希表记录顶点的前驱MapVertex,VertexpreVertexnew HashMap();//利用哈希表记录起点到任意一点的最短路径MapVertex,IntegerminPathnew HashMap();//初始化三个表for(int i0;ivertexs.size();i){//初始化每一个点都未走过visited.put(vertexs.get(i),false);//初始化每个点的前驱都是自己preVertex.put(vertexs.get(i),vertexs.get(i));//初始化起点到任意两个点之间的最短路径都是无穷大minPath.put(vertexs.get(i),INF);}Vertex startVertexvertexs_map.get(start);Vertex endVertexvertexs_map.get(end);//填充存在的路径for(int i0;istartVertex.neighborVertexs.size();i){//设置起点与邻居节点之间的权值minPath.put(startVertex.neighborVertexs.get(i),startVertex.weights.get(startVertex.neighborVertexs.get(i)));//设置点前驱preVertex.put(startVertex.neighborVertexs.get(i),startVertex);}//自己到自己的距离为0minPath.put(startVertex,0);Vertex curVertexnull;//一直寻路直到找到终点while(curVertex!endVertex){Integer minWeightInteger.MAX_VALUE;curVertexnull;//能看到的点之间选取距离最小的那个,且这个点并没有走过for(Vertex v:minPath.keySet()){if(!visited.get(v)minPath.get(v)minWeight){//切换中心点curVertexv;//更新最小权值minWeightminPath.get(v);}}//如果找不到下一个中心点说明从起点根本到达不来终点if(curVertexnull)return null;//标记选取点visited.put(curVertex,true);//更新权值for(int i0;icurVertex.neighborVertexs.size();i){//邻居节点Vertex neighborVertexcurVertex.neighborVertexs.get(i);//计算起点到邻居节点之间新的权值int newWeightminPath.get(curVertex)curVertex.weights.get(neighborVertex);//找到能移动的点,如果转折之后距离更短则记录更短的距离if(visited.get(neighborVertex)falsenewWeightminPath.get(neighborVertex)){//记录更短距离minPath.put(neighborVertex,newWeight);//记录邻居节点的前驱preVertex.put(neighborVertex,curVertex);}}}//起点到终点之间的最短路径LinkedListVertextargetPathnew LinkedList();for(Vertex curVerendVertex;curVer!startVertex;curVerpreVertex.get(curVer)){targetPath.addFirst(curVer);}targetPath.addFirst(startVertex);//拼接最短路径StringBuffer minPathStringBuffernew StringBuffer();Integer pathSum0;for(int i0;i targetPath.size();i){minPathStringBuffer.append(targetPath.get(i).Number);if(i! targetPath.size()-1){pathSumpathSumtargetPath.get(i).weights.get(targetPath.get(i1));minPathStringBuffer.append(-);}}return new MinPathResult(targetPath, minPathStringBuffer.toString(),pathSum);}
}
测试函数
import java.util.*;public class Main {public static void main(String[] args) {Scanner scannernew Scanner(System.in);ListVertexvertexsnew LinkedList();ListEdgeedgesnew LinkedList();System.out.println(请输入顶点的数量:);Integer vexcnt scanner.nextInt();System.out.println(请输入这些顶点编号:);for(int i0;ivexcnt;i){vertexs.add(new Vertex(scanner.next()));}System.out.println(请输入边的数量);Integer edgecnt scanner.nextInt();System.out.println(请输入这些边的端点编号和权值:);for(int i0;iedgecnt;i){String number1 scanner.next();String number2 scanner.next();Integer weight scanner.nextInt();Vertex v1null;Vertex v2null;for(int j0;jvertexs.size();j){if(vertexs.get(j).Number.equals(number1))v1vertexs.get(j);if(vertexs.get(j).Number.equals(number2))v2vertexs.get(j);}edges.add(new Edge(v1,v2,weight));}//定义迪杰斯特拉操作类DijkstraOperator dijkstranew DijkstraOperator(vertexs,edges);//获取任意两点之间的最短路径结果集ListMinPathResultminPathResultsnew ArrayList();for(int i0;i vertexs.size();i){for(int ji1;j vertexs.size();j){minPathResults.add(dijkstra.getMinPath(vertexs.get(i).Number,vertexs.get(j).Number));System.out.println(minPathResults.get(minPathResults.size()-1));}}}
}
测试输入与输出结果
//输入部分
请输入顶点的数量:
7
请输入这些顶点编号:
A B C D E F G
请输入边的数量
12
请输入这些边的端点编号和权值:
A B 12
A F 16
A G 14
B C 10
B F 7
G F 9
G E 8
F C 6
F E 2
C D 3
C E 5
E D 4//输出部分
Result{minPathString:A-B minPathSum:12}
Result{minPathString:A-B-C minPathSum:22}
Result{minPathString:A-F-E-D minPathSum:22}
Result{minPathString:A-F-E minPathSum:18}
Result{minPathString:A-F minPathSum:16}
Result{minPathString:A-G minPathSum:14}
Result{minPathString:B-C minPathSum:10}
Result{minPathString:B-F-E-D minPathSum:13}
Result{minPathString:B-F-E minPathSum:9}
Result{minPathString:B-F minPathSum:7}
Result{minPathString:B-F-G minPathSum:16}
Result{minPathString:C-D minPathSum:3}
Result{minPathString:C-E minPathSum:5}
Result{minPathString:C-F minPathSum:6}
Result{minPathString:C-E-G minPathSum:13}
Result{minPathString:D-E minPathSum:4}
Result{minPathString:D-E-F minPathSum:6}
Result{minPathString:D-E-G minPathSum:12}
Result{minPathString:E-F minPathSum:2}
Result{minPathString:E-G minPathSum:8}
Result{minPathString:F-G minPathSum:9}进程已结束退出代码为 0
