菜单

Dijkstra

2018年11月15日 - jQuery

原创

在押本身之笔记吧


 

  Dijkstra算法用于求最好缺乏路径。

http://note.youdao.com/groupshare/?token=A9CCF20788BE4B408F525FCD5F24CCB7&gid=16050585

  图片 1

  用邻接矩阵存储图,若要1顶另外顶点的卓绝缺少路径,用数组dis存储1交任何顶点的无比短缺路径。

  dis初始化即至点1及另外顶点的发端距离,不直相接的尽管为无根本大,**齐图中dis初始化为0/15/10/16/30。**

  接下由数组dis中选出一个最为小值,上图备受呢10(0乎到自我的相距),则1顶3之极端短距离即为10,理解

立刻无异触及很关键,因为跟1直相接的点吃距离最小的极是3,距离是10,若通过外顶点其余路径到达3,距离

还见面超过10,所以1到顶点3底顶差路径已经认可了,以后不管需创新。

  确认了就漫长太短路径,比较完美利用其,看看1经这长达最缺少路程径能不能够缩短1至任何顶点的离开,比如达图

受1顶5底偏离呢30,但是透过极端缺少路径1交3重到5纵可知缩短1都5之离开,其余边也如逐个判断缩小,此过程叫“松弛”。

  Dijkstra求最短路径的主干步骤如下:

  1.  用拥有的极限分为两片段:已了解最缺路径的极端集合P和茫然最短路径的终点集合Q。最初步,已清楚最缺少路径

    的终端集合P中特发源点一个极限。我们这边用一个book数组来记录哪些点当集合P中。例如对于有顶点i,如

    果book[i]为1则代表这极端在集合P中,反之,则以集合Q中。

  2.  装置源点s到好之太差路径也0哪怕dis[s]=0.若存在有源点能一直抵达的顶点i,则拿dis[i]设为matrix[s][i],

    matrix为邻接矩阵。同时把所有其他(源点不克一直到的)顶点的无比缺少路程径设为∞。

  3.  在集合Q的有所终端中甄选一个离源点s最近的顶点u(即dis[u]绝小)加入到集合P中。并察看所有以点u为起点的边,

    对各国一样漫长边进行松弛操作。例如有一样漫漫由u到v的限度,那么可以经过以边u-v添加到尾来开展同等条从s到v的门道,这

    长达路子的长度是dis[u]+e[u][v]。如果这价比较目前早已掌握的dis[v]的价如果聊,我们可用新值来替代当前dis[v]中的值。

  4.  双重第3步,如果集合Q为空,算法结束。最终dis数组中的价值就是是源点到持有终端的太短缺路径。

 1 import java.util.*;
 2 
 3 public class Dijkstra {
 4     
 5     static int v;    //顶点
 6     static int e;    //边
 7     static int aim;    //aim与其余顶点的最短路径
 8     static int matrix[][];    //邻接矩阵
 9     static int book[];    //标记数组
10     static int dis[];    //存储与其他顶点的距离
11     static int min=99999;
12     static int inf=99999;
13 
14     public static void main(String[] args) {
15         Scanner reader=new Scanner(System.in);
16         v=reader.nextInt();
17         e=reader.nextInt();
18         aim=reader.nextInt();
19         matrix=new int[v+1][v+1];    //从1开始编号
20         book=new int[v+1];
21         dis=new int[v+1];
22         //矩阵初始化
23         for(int i=1;i<=v;i++) {
24             book[i]=0;
25             for(int j=1;j<=v;j++) {
26                 if(i==j) {
27                     matrix[i][j]=0;
28                 }
29                 else {
30                     matrix[i][j]=inf;
31                 }
32             }
33         }
34         book[aim]=1;    //求aim到其余顶点的距离
35         //读入边
36         for(int i=1;i<=e;i++) {
37             int first_City=reader.nextInt();
38             int second_City=reader.nextInt();
39             int value=reader.nextInt();
40             matrix[first_City][second_City]=value;    //有向图
41         }
42         //数组dis初始化
43         for(int i=1;i<=v;i++) {
44             dis[i]=matrix[aim][i];
45         }
46         for(int i=1;i<=v-1;i++) {    //循环v-1次,每次确认一个顶点
47             int u=-1;
48             min=inf;
49             //寻找距离aim最近的点
50             for(int j=1;j<=v;j++) {
51                 if(book[j]==0 && dis[j]<min) {
52                     min=dis[j];
53                     u=j;
54                 }
55             }
56             if(u==-1) {
57                 break;
58             }
59             book[u]=1;    //确认顶点u
60             //松弛
61             for(int z=1;z<=v;z++) {
62                 if(matrix[u][z]<inf) {
63                     if(dis[z]>dis[u]+matrix[u][z]) {    //更新距离
64                         dis[z]=dis[u]+matrix[u][z];
65                     }
66                 }
67             }
68         }
69         for(int i=1;i<=v;i++) {
70             System.out.print(dis[i]+" ");
71         }
72     }
73 
74 }

14:32:02

2018-07-29

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图