Dijkstra算法——通过边实现松弛

时间:2021-06-21 11:00:40

Dijkstra算法——通过边实现松弛

Dijkstra算法——通过边实现松弛Dijkstra算法——通过边实现松弛
 1 import java.util.Scanner;
 2 import java.util.LinkedList;
 3 import java.util.LinkedList;
 4 import java.util.Scanner;
 5 import java.util.TreeSet;
 6 import java.util.Scanner;
 7 public class One {
 8     public static void main(String args[]){
 9         int n,r;
10         Scanner scanner=new Scanner(System.in);
11         System.out.println("请输入点数、边:");
12         n=scanner.nextInt();
13         r=scanner.nextInt();
14         int a[][]=new int[n+1][n+1];//存放路径路程的二维数组
15         int dis[]=new int[n+1];//用于标记源点1到各点的距离
16         int book[]=new int[n+1];//book[i]=1表示i点在集合p(确定源点到该点的最短路径)中,否则在集合q中
17         //初始化二维数组
18         for(int i=1;i<=n;i++){
19             for(int j=1;j<=n;j++){
20                 if(i==j)a[i][j]=0;
21                 else a[i][j]=999;//999为无穷大,表示i到j没有直达路径
22             }
23         }
24         System.out.println("请输入各边(有向)以及该边的距离:");
25         for(int i=1;i<=r;i++){
26             int x=scanner.nextInt();
27             int y=scanner.nextInt();
28             int d=scanner.nextInt();
29             a[x][y]=d;
30         }
31         
32         //Dijkstra算法
33         //设定各项初值
34         book[1]=1;//源点,其余为0
35         //初始化dis
36         for(int i=1;i<=n;i++)dis[i]=a[1][i];
37         //sum用来计算book里面确定了最短源-点路径的数目,若为n,说明全部的源点到所有点的最短距离都确定
38         int sum=1, j=0;
39         while(true){
40             int min=999;
41             for(int i=2;i<=n;i++){
42                 if(book[i]==0&&min>dis[i]){
43                     min=dis[i];//求未定的离源点最短路程的点
44                     j=i;//用于下个中转(松弛)
45                 }
46             }
47             book[j]=1;
48             sum++;
49             if(sum==n)break;
50             //松弛
51             for(int i=2;i<=n;i++){
52                 if(book[i]==0&&dis[i]>(dis[j]+a[j][i]))dis[i]=dis[j]+a[j][i];
53             }
54         }
55         for(int i=1;i<=n;i++)System.out.print(dis[i]+" ");
56     }
57 }
Dijkstra算法

代码结果:

Dijkstra算法——通过边实现松弛