Pastebin.vip

A Dijstra algorithm (single source shortest path algorithm, Dijkstra algorithm) written in Java.

From , 3 Years ago, written in Java, viewed 165 times.
URL https://pastebin.vip/view/d01eeca8
  1. package Test;
  2.  
  3. import java.util.TreeMap;
  4. import java.util.ArrayList;
  5. import java.io.BufferedReader;
  6. import java.io.InputStreamReader;
  7. import java.io.IOException;
  8.  
  9. class Point {
  10.         private int id;// 点的id
  11.         private boolean flag = false;// 标志是否被遍历
  12.         int sum;// 记录总的点个数
  13.  
  14.         private TreeMap<Integer, Integer> thisPointMap = new TreeMap<Integer, Integer>();// 该点到各点的距离。
  15.         BufferedReader bufr = new BufferedReader(new InputStreamReader(System.in));
  16.  
  17.         Point(int sum) { // 构造函数 带有顶点个数
  18.                 this.sum = sum;
  19.         }
  20.  
  21.         public void setId(int id) {// 设置顶点id
  22.                 this.id = id;
  23.         }
  24.  
  25.         public int getId() {// 获得顶点id
  26.                 return this.id;
  27.         }
  28.  
  29.         public void changeFlag() {// 修改访问状态。
  30.                 this.flag = true;
  31.         }
  32.  
  33.         public boolean isVisit() {// 查看访问状态
  34.                 return flag;
  35.         }
  36.  
  37.         public void setLenToOther()throws IOException{// 初始化改点到各顶点的距离。
  38.                 System.out.println("=======请输入顶点" + (this.id + 1) + "至其他各顶点的边距=======");
  39.                 for (int i = 0; i < sum; i++) {
  40.                         if (i == this.id)
  41.                                 thisPointMap.put(this.id, 0);
  42.                         else {
  43.                                 System.out.print("至 顶点" + (i + 1) + " 的距离 ：");
  44.                                 boolean flag =true;
  45.                                 int len = 0;
  46.                                 while(flag){
  47.                                         try {
  48.                                                 len = Integer.valueOf(bufr.readLine());
  49.                                                 flag = false;
  50.                                         } catch (NumberFormatException e) {
  51.                                                 System.out.print("输入有误，请重新输入：");
  52.                                         }
  53.                                 };
  54.                                 thisPointMap.put(i, len);
  55.                         }
  56.                 }
  57.         }
  58.  
  59.         // 该点到顶尖id的 距离。
  60.         public int lenToPointId(int id) {
  61.                 return thisPointMap.get(id);
  62.         }
  63. }
  64.  
  65. class Dijkstra {
  66.         public static void main(String[] args)throws IOException {
  67.                 ArrayList<Point> point_arr = new ArrayList<Point>();// 存储点集合
  68.                 BufferedReader bufr = new BufferedReader(new InputStreamReader(System.in));
  69.                 System.out.print("请输入顶点个数： ");
  70.                 int sum = 0;
  71.                 boolean flag =true;
  72.                 while(flag){
  73.                         try {
  74.                                 sum = Integer.valueOf(bufr.readLine());
  75.                                 flag = false;
  76.                         } catch (NumberFormatException e) {
  77.                                 System.out.print("输入有误，请重新输入：");
  78.                         }
  79.                 };
  80.                 for (int i = 0; i < sum; i++) {// 初始化
  81.                         Point p = new Point(sum);
  82.                         p.setId(i);
  83.                         p.setLenToOther();
  84.                         point_arr.add(p);
  85.                 }
  86.                 System.out.print("请输入起始顶点 id ：");
  87.                 boolean flag2 =true;
  88.                 int start = 0;
  89.                 while(flag2){
  90.                         try {
  91.                                 start = Integer.valueOf(bufr.readLine())-1;
  92.                                 if(start > sum-1 || start < 0)
  93.                                         throw new NumberFormatException();
  94.                                 flag2 = false;
  95.                         }catch (NumberFormatException e) {
  96.                                 System.out.print("输入有误，请重新输入：");
  97.                         }
  98.                 };
  99.                 showDijkstra(point_arr, start);// 单源最短路径遍历
  100.         }
  101.  
  102.         public static void showDijkstra(ArrayList<Point> arr, int i) {
  103.                 System.out.print("顶点" + (i + 1));
  104.                 arr.get(i).changeFlag();
  105.                 Point p1 = getTopointMin(arr, arr.get(i));
  106.                 if (p1 == null)
  107.                         return;
  108.                 int id = p1.getId();
  109.                 showDijkstra(arr, id);
  110.  
  111.         }
  112.  
  113.         public static Point getTopointMin(ArrayList<Point> arr, Point p) {
  114.                 Point temp = null;
  115.                 int minLen = Integer.MAX_VALUE;
  116.                 for (int i = 0; i < arr.size(); i++) {
  117.                         // 当已访问 或 者是自身或者无该路径时跳过。
  118.                         if (arr.get(i).isVisit() || arr.get(i).getId() == p.getId() || p.lenToPointId(i) < 0)
  119.                                 continue;
  120.                         else {
  121.                                 if (p.lenToPointId(i) < minLen) {
  122.                                         minLen = p.lenToPointId(i);
  123.                                         temp = arr.get(i);
  124.                                 }
  125.                         }
  126.                 }
  127.                 if (temp == null)
  128.                         return temp;
  129.                 else
  130.                         System.out.print("  @--" + minLen + "--> ");
  131.                 return temp;
  132.         }
  133. }
  134.  
  135. {--
  136. //java/5968

Reply to "A Dijstra algorithm (single source shortest path algorithm, Dijkstra algorithm) written in Java."

Here you can reply to the paste above

captcha

https://burned.cc - Burn After Reading Website
Powered by Pastebin.vip paste tool since 2022!