Dijkstra算法求最短路径_基于 dijsktra 算法的最短路径求解

作者：笔触狂放9 | 2024-06-13 05:17:19

踩

基于 dijsktra 算法的最短路径求解

定义点node对象

/**
 * desc: 路网图中的点 <node>节点</node>
 *
 * @author qts
 * @date 2022/7/14 0014
 */
@Data
@Builder
public class Node implements Serializable {
    private static final long serialVersionUID = 1L;

    private String id;

    /**
     * 纬度
     */
    private String lat;

    /**
     * 经度
     */
    @JsonProperty("lng")
    private String lon;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

定义路 way对象

/**
 * desc: 路网图中的 路
 *
 * @author qts
 * @date 2022/7/14 0014
 */
@Data
@Builder
public class Way implements Serializable {
    private static final long serialVersionUID = 1L;

    private String id;

    /**
     * node 点集合
     */
    private List<Node> nodes;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

OsmUtil 路网数据处理工具

实际是对xml文件的解析,路网数据可以从中国路网中下载,也可以根据实际情况,手动绘制,需要特定的工具,自行百度

package com.fillke.business.util;

import com.fillke.business.dijkstra.Node;
import com.fillke.business.dijkstra.Way;
import org.dom4j.Element;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * desc: osm 文件处理 工具
 *  用于获取osm 文件中的路网数据
 *
 * @author qts
 * @date 2022/7/18 0018
 */
public class OsmUtil {
    public static final String OSM_PATH = "D:\\osm_file\\teng.osm";
    private OsmUtil() {
    }

    /**
     * 获取osm中的所有node节点
     * @param path osm的 文件 路径
     * @return node节点集合
     * @throws Exception
     */
    public static List<Node> getAllNode(String path) throws Exception {
        // 获取List<Node>节点集合
        List<Element> nodeElements = XmlUtils.getElementList(path, "node");
        List<Node> nodeList = new ArrayList<Node>();
        nodeElements.forEach(e -> {
            String action = e.attributeValue("action");
            // 排除删除的节点
            if (!"delete".equals(action)) {

                Node node = Node.builder().id( e.attributeValue("id"))
                    .lat(e.attributeValue("lat"))
                    .lon(e.attributeValue("lon"))
                    .build();

                nodeList.add(node);
            }
        });
        return nodeList;
    }

    /**
     * 获取osm文件中的所有 道路信息列表
     * @param path osm路网文件
     * @param nodeList 所有节点列表
     * @return Way 列表
     * @throws Exception
     */
    public static List<Way> getAllWay(String path, List<Node> nodeList) throws Exception {
        // 获取 List<Way> 所有路的集合
        List<Element> wayElements = XmlUtils.getElementList(path, "way");
        List<Way> wayList = new ArrayList<Way>();
        Way way;
        List<Node> nodes;
        List<Node> ref;
        String action;
        List<Element> ndElements;
        // 遍历wayElements
        for (Element wayElement : wayElements) {
            action = wayElement.attributeValue("action");
            // 排除删除的道路
            if (!"delete".equals(action)) {
                // 获取way下的nd节点集合,nd中的ref属性为node节点中的id值
                ndElements = wayElement.elements("nd");
                nodes = new ArrayList<Node>();
                // 遍历ndElements封装List<Node>
                for (Element ndElement : ndElements) {
                    // 通过ref查询对应的node,添加到way对象中
                    ref = nodeList.stream().filter(e -> e.getId().equals(ndElement.attributeValue("ref")))
                        .collect(Collectors.toList());
                    if (ref.size() > 0) {
                        nodes.add(ref.get(0));
                    }
                }
                // 每条路数据
                way = Way.builder()
                    .id(wayElement.attributeValue("id"))
                    .nodes(nodes).build();

                // 添加到路集合中
                wayList.add(way);
            }
        }
        return wayList;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

teng.osm文件(路网数据)

其中

node 代表所有点
way: 代表路, nd 代表路包含的点,ref属性指向对应的node的id属性
可通过以上方法分装成对象列表,用于后续算法使用

<?xml version='1.0' encoding='UTF-8'?>
<osm version='0.6' upload='false' generator='JOSM'>
  <node id='-102797' lat='29.7119563' lon='106.5760958' />
  <node id='-102798' lat='29.7126345' lon='106.5762145' />
  <node id='-102799' action='modify' lat='29.71476262768' lon='106.57289243586' />
  <node id='-102800' action='modify' lat='29.71321234358' lon='106.57196114811' />
  <node id='-102801' action='modify' lat='29.71200442083' lon='106.57121261115' />
  <node id='-102802' action='modify' lat='29.71151327632' lon='106.57091931054' />
  <node id='-102803' action='modify' lat='29.70928799385' lon='106.57169316241' />
  <node id='-102804' lat='29.70923266449' lon='106.57178423484' />
  <node id='-102805' action='modify' lat='29.70925026214' lon='106.57375385082' />
  <node id='-102806' action='modify' lat='29.70923677758' lon='106.57603539036' />
  <node id='-102807' lat='29.7135815' lon='106.5770336' />
  <node id='-102808' lat='29.713672' lon='106.5767924' />
  <node id='-102809' lat='29.7137297' lon='106.5766644' />
  <node id='-102810' lat='29.7145073' lon='106.5749385' />
  <node id='-102811' lat='29.7147178' lon='106.5744712' />
  <node id='-102812' lat='29.7148393' lon='106.5740852' />
  <node id='-102813' lat='29.714903' lon='106.5737294' />
  <node id='-102814' lat='29.7149079' lon='106.5731456' />
  <node id='-102815' lat='29.7149062' lon='106.5730227' />
  <node id='-102816' lat='29.7149013' lon='106.5714388' />
  <node id='-102817' lat='29.714892' lon='106.5701094' />
  <node id='-102818' lat='29.714888' lon='106.5697368' />
  <node id='-102819' lat='29.7149058' lon='106.5691011' />
  <node id='-102820' lat='29.7149718' lon='106.568797' />
  <node id='-102821' lat='29.7152246' lon='106.5681194' />
  <node id='-102822' lat='29.7153153' lon='106.5678761' />
  <node id='-102823' lat='29.7075331' lon='106.5761278' />
  <node id='-102824' lat='29.7078532' lon='106.5761344' />
  <node id='-102825' lat='29.711956' lon='106.5759916' />
  <node id='-102826' lat='29.71153326048' lon='106.57597860029' />
  <node id='-102827' lat='29.71038571783' lon='106.57598606678' />
  <node id='-102828' lat='29.7083483' lon='106.5759853' />
  <node id='-102829' lat='29.7080817' lon='106.5759772' />
  <node id='-102830' lat='29.7078421' lon='106.5759692' />
  <node id='-102831' action='modify' lat='29.71155817376' lon='106.57374212125' />
  <node id='-102832' lat='29.711547' lon='106.5692389' />
  <node id='-102833' action='modify' lat='29.711567128' lon='106.56903201575' />
  <node id='-102834' action='modify' lat='29.71164051937' lon='106.56862478311' />
  <node id='-102835' action='modify' lat='29.71172701413' lon='106.568343404' />
  <node id='-102836' action='modify' lat='29.71229200189' lon='106.56675200711' />
  <node id='-102837' action='modify' lat='29.71239447448' lon='106.56649491956' />
  <node id='-102838' lat='29.708071' lon='106.5761388' />
  <node id='-102839' lat='29.7083462' lon='106.5761376' />
  <node id='-102840' lat='29.7090496' lon='106.5761461' />
  <node id='-102841' lat='29.7093707' lon='106.5760721' />
  <node id='-102842' lat='29.7115564' lon='106.5760758' />
  <node id='-102843' action='modify' lat='29.71250124998' lon='106.57608683412' />
  <node id='-102844' action='modify' lat='29.71245796196' lon='106.57369017887' />
  <node id='-102845' lat='29.7131667' lon='106.5764628' />
  <node id='-102846' lat='29.7135704' lon='106.5767358' />
  <node id='-102847' lat='29.71467' lon='106.5773567' />
  <node id='-102848' lat='29.7153078' lon='106.5775699' />
  <node id='-102849' lat='29.7158601' lon='106.5776229' />
  <node id='-102850' lat='29.7181616' lon='106.5776465' />
  <node id='-102851' lat='29.7182376' lon='106.5776477' />
  <node id='-102852' lat='29.7197448' lon='106.5776368' />
  <node id='-102853' lat='29.7200439' lon='106.5776346' />
  <node id='-102854' lat='29.7201931' lon='106.5776127' />
  <node id='-102855' lat='29.720456' lon='106.5775187' />
  <node id='-102856' lat='29.7220244' lon='106.5768398' />
  <node id='-102857' lat='29.7231512' lon='106.5763322' />
  <node id='-102858' lat='29.7232307' lon='106.5763022' />
  <node id='-102859' lat='29.7237898' lon='106.5760866' />
  <node id='-102860' lat='29.7242039' lon='106.5759709' />
  <node id='-102861' lat='29.7248137' lon='106.5758987' />
  <node id='-102862' lat='29.7261306' lon='106.5759003' />
  <node id='-102863' lat='29.7264573' lon='106.5759014' />
  <node id='-102864' lat='29.7265866' lon='106.575902' />
  <node id='-102865' lat='29.7269312' lon='106.5759005' />
  <node id='-102866' lat='29.7278756' lon='106.5759007' />
  <node id='-102867' lat='29.7292854' lon='106.5759079' />
  <node id='-102868' lat='29.7293739' lon='106.575879' />
  <node id='-102869' lat='29.7313996' lon='106.575167' />
  <node id='-102870' lat='29.7328503' lon='106.5746722' />
  <node id='-102871' lat='29.7329502' lon='106.5746379' />
  <node id='-102872' lat='29.715173' lon='106.567819' />
  <node id='-102873' lat='29.7150912' lon='106.5680647' />
  <node id='-102874' lat='29.7148496' lon='106.5687908' />
  <node id='-102875' lat='29.71481' lon='106.5690826' />
  <node id='-102876' lat='29.7147844' lon='106.5697355' />
  <node id='-102877' lat='29.71478558069' lon='106.57010846661' />
  <node id='-102878' lat='29.7147898' lon='106.5714413' />
  <node id='-102879' lat='29.7147888' lon='106.5731808' />
  <node id='-102880' lat='29.7147825' lon='106.5737293' />
  <node id='-102881' lat='29.7147298' lon='106.5741037' />
  <node id='-102882' lat='29.7146404' lon='106.5744145' />
  <node id='-102883' action='modify' lat='29.71441411007' lon='106.57495536444' />
  <node id='-102884' lat='29.713633' lon='106.5765999' />
  <node id='-102885' lat='29.7134668' lon='106.5769629' />
  <node id='-102886' lat='29.7329221' lon='106.574528' />
  <node id='-102887' lat='29.732822' lon='106.5745613' />
  <node id='-102888' lat='29.7313719' lon='106.575057' />
  <node id='-102889' lat='29.7293521' lon='106.5757512' />
  <node id='-102890' lat='29.7292651' lon='106.5757817' />
  <node id='-102891' lat='29.7278723' lon='106.5757891' />
  <node id='-102892' lat='29.7269317' lon='106.5757863' />
  <node id='-102893' lat='29.726586' lon='106.5757798' />
  <node id='-102894' lat='29.7264555' lon='106.5757799' />
  <node id='-102895' lat='29.7261371' lon='106.5757784' />
  <node id='-102896' lat='29.7252364' lon='106.5757725' />
  <node id='-102897' lat='29.725152' lon='106.5757721' />
  <node id='-102898' lat='29.7248029' lon='106.5757699' />
  <node id='-102899' lat='29.7241787' lon='106.5758493' />
  <node id='-102900' lat='29.7237635' lon='106.5759645' />
  <node id='-102901' lat='29.7231938' lon='106.5761783' />
  <node id='-102902' lat='29.7231467' lon='106.5761959' />
  <node id='-102903' lat='29.7231118' lon='106.5762116' />
  <node id='-102904' lat='29.722117' lon='106.5766572' />
  <node id='-102905' lat='29.7204344' lon='106.577387' />
  <node id='-102906' lat='29.720174' lon='106.5774796' />
  <node id='-102907' lat='29.7200269' lon='106.5775058' />
  <node id='-102908' lat='29.7197598' lon='106.5775076' />
  <node id='-102909' lat='29.7182378' lon='106.5775171' />
  <node id='-102910' lat='29.7181619' lon='106.5775164' />
  <node id='-102911' lat='29.7170578' lon='106.577512' />
  <node id='-102912' lat='29.7159162' lon='106.5775041' />
  <node id='-102913' lat='29.715317' lon='106.5774582' />
  <node id='-102914' lat='29.7147015' lon='106.5772487' />
  <node id='-102915' lat='29.7131763' lon='106.576349' />
  <node id='-102916' action='modify' lat='29.71038855219' lon='106.57375289048' />
  <node id='-102917' lat='29.7075331' lon='106.5759605' />
  <node id='-102918' action='modify' lat='29.7081341362' lon='106.57399970711' />
  <node id='-102919' action='modify' lat='29.70877928143' lon='106.57383069289' />
  <node id='-102952' action='modify' lat='29.71199008196' lon='106.56754632853' />
  <node id='-102999' action='modify' lat='29.71213939876' lon='106.56715450679' />
  <way id='-102493'>
    <nd ref='-102797' />
    <nd ref='-102798' />
    <tag k='bridge' v='yes' />
    <tag k='highway' v='primary' />
    <tag k='lanes' v='3' />
    <tag k='layer' v='1' />
    <tag k='name' v='公园西路' />
    <tag k='name:en' v='West Park Road' />
    <tag k='oneway' v='yes' />
  </way>
  <way id='-102494'>
    <nd ref='-102799' />
    <nd ref='-102800' />
    <nd ref='-102801' />
    <nd ref='-102802' />
    <nd ref='-102803' />
    <nd ref='-102804' />
    <nd ref='-102805' />
    <nd ref='-102806' />
    <tag k='highway' v='tertiary' />
    <tag k='name' v='纵二路' />
    <tag k='noref' v='yes' />
  </way>
  <way id='-102495'>
    <nd ref='-102807' />
    <nd ref='-102808' />
    <nd ref='-102809' />
    <nd ref='-102810' />
    <nd ref='-102811' />
    <nd ref='-102812' />
    <nd ref='-102813' />
    <nd ref='-102814' />
    <nd ref='-102815' />
    <nd ref='-102816' />
    <nd ref='-102817' />
    <nd ref='-102818' />
    <nd ref='-102819' />
    <nd ref='-102820' />
    <nd ref='-102821' />
    <nd ref='-102822' />
    <tag k='highway' v='secondary' />
    <tag k='lanes' v='3' />
    <tag k='name' v='腾芳大道' />
    <tag k='oneway' v='yes' />
  </way>
  <way id='-102496'>
    <nd ref='-102823' />
    <nd ref='-102824' />
    <tag k='highway' v='primary' />
    <tag k='oneway' v='yes' />
  </way>
  <way id='-102497'>
    <nd ref='-102825' />
    <nd ref='-102826' />
    <nd ref='-102827' />
    <nd ref='-102806' />
    <nd ref='-102828' />
    <nd ref='-102829' />
    <nd ref='-102830' />
    <tag k='highway' v='primary' />
    <tag k='lanes' v='3' />
    <tag k='name' v='公园西路' />
    <tag k='name:en' v='West Park Road' />
    <tag k='oneway' v='yes' />
  </way>
  <way id='-102498' action='modify'>
    <nd ref='-102826' />
    <nd ref='-102831' />
    <nd ref='-102802' />
    <nd ref='-102832' />
    <nd ref='-102833' />
    <nd ref='-102834' />
    <nd ref='-102835' />
    <nd ref='-102952' />
    <nd ref='-102999' />
    <nd ref='-102836' />
    <nd ref='-102837' />
    <tag k='construction' v='tertiary' />
    <tag k='highway' v='tertiary' />
  </way>
  <way id='-102499'>
    <nd ref='-102824' />
    <nd ref='-102838' />
    <nd ref='-102839' />
    <nd ref='-102840' />
    <nd ref='-102841' />
    <nd ref='-102842' />
    <nd ref='-102797' />
    <tag k='highway' v='primary' />
    <tag k='lanes' v='3' />
    <tag k='name' v='公园西路' />
    <tag k='name:en' v='West Park Road' />
    <tag k='oneway' v='yes' />
  </way>
  <way id='-102500'>
    <nd ref='-102843' />
    <nd ref='-102844' />
    <nd ref='-102800' />
    <tag k='highway' v='tertiary' />
    <tag k='noref' v='yes' />
  </way>
  <way id='-102501'>
    <nd ref='-102798' />
    <nd ref='-102845' />
    <nd ref='-102846' />
    <nd ref='-102808' />
    <nd ref='-102847' />
    <nd ref='-102848' />
    <nd ref='-102849' />
    <nd ref='-102850' />
    <nd ref='-102851' />
    <nd ref='-102852' />
    <nd ref='-102853' />
    <nd ref='-102854' />
    <nd ref='-102855' />
    <nd ref='-102856' />
    <nd ref='-102857' />
    <nd ref='-102858' />
    <nd ref='-102859' />
    <nd ref='-102860' />
    <nd ref='-102861' />
    <nd ref='-102862' />
    <nd ref='-102863' />
    <nd ref='-102864' />
    <nd ref='-102865' />
    <nd ref='-102866' />
    <nd ref='-102867' />
    <nd ref='-102868' />
    <nd ref='-102869' />
    <nd ref='-102870' />
    <nd ref='-102871' />
    <tag k='highway' v='primary' />
    <tag k='lanes' v='3' />
    <tag k='name' v='公园西路' />
    <tag k='name:en' v='West Park Road' />
    <tag k='oneway' v='yes' />
  </way>
  <way id='-102502'>
    <nd ref='-102822' />
    <nd ref='-102872' />
    <nd ref='-102873' />
    <nd ref='-102874' />
    <nd ref='-102875' />
    <nd ref='-102876' />
    <nd ref='-102877' />
    <nd ref='-102878' />
    <nd ref='-102799' />
    <nd ref='-102879' />
    <nd ref='-102880' />
    <nd ref='-102881' />
    <nd ref='-102882' />
    <nd ref='-102883' />
    <nd ref='-102884' />
    <nd ref='-102846' />
    <nd ref='-102885' />
    <tag k='highway' v='secondary' />
    <tag k='lanes' v='3' />
    <tag k='name' v='腾芳大道' />
    <tag k='oneway' v='yes' />
  </way>
  <way id='-102503'>
    <nd ref='-102886' />
    <nd ref='-102887' />
    <nd ref='-102888' />
    <nd ref='-102889' />
    <nd ref='-102890' />
    <nd ref='-102891' />
    <nd ref='-102892' />
    <nd ref='-102893' />
    <nd ref='-102894' />
    <nd ref='-102895' />
    <nd ref='-102896' />
    <nd ref='-102897' />
    <nd ref='-102898' />
    <nd ref='-102899' />
    <nd ref='-102900' />
    <nd ref='-102901' />
    <nd ref='-102902' />
    <nd ref='-102903' />
    <nd ref='-102904' />
    <nd ref='-102905' />
    <nd ref='-102906' />
    <nd ref='-102907' />
    <nd ref='-102908' />
    <nd ref='-102909' />
    <nd ref='-102910' />
    <nd ref='-102911' />
    <nd ref='-102912' />
    <nd ref='-102913' />
    <nd ref='-102914' />
    <nd ref='-102809' />
    <nd ref='-102884' />
    <nd ref='-102915' />
    <nd ref='-102843' />
    <tag k='highway' v='primary' />
    <tag k='lanes' v='3' />
    <tag k='name' v='公园西路' />
    <tag k='name:en' v='West Park Road' />
    <tag k='oneway' v='yes' />
  </way>
  <way id='-102504'>
    <nd ref='-102916' />
    <nd ref='-102827' />
    <tag k='highway' v='tertiary' />
    <tag k='noref' v='yes' />
  </way>
  <way id='-102505'>
    <nd ref='-102830' />
    <nd ref='-102917' />
    <tag k='highway' v='primary' />
    <tag k='oneway' v='yes' />
  </way>
  <way id='-102506'>
    <nd ref='-102843' />
    <nd ref='-102825' />
    <tag k='bridge' v='yes' />
    <tag k='highway' v='primary' />
    <tag k='lanes' v='3' />
    <tag k='layer' v='1' />
    <tag k='name' v='公园西路' />
    <tag k='name:en' v='West Park Road' />
    <tag k='oneway' v='yes' />
  </way>
  <way id='-102507'>
    <nd ref='-102877' />
    <nd ref='-102817' />
    <tag k='highway' v='secondary' />
    <tag k='noref' v='yes' />
  </way>
  <way id='-102508'>
    <nd ref='-102918' />
    <nd ref='-102919' />
    <nd ref='-102805' />
    <nd ref='-102916' />
    <nd ref='-102831' />
    <nd ref='-102844' />
    <nd ref='-102883' />
    <tag k='construction' v='tertiary' />
    <tag k='highway' v='tertiary' />
    <tag k='name' v='纵一路' />
  </way>
</osm>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371

Dijkstra算法工具

package com.fillke.business.dijkstra;

import com.fillke.business.util.*;

import java.util.*;

/**
 * @author qts
 * @create 2022-07-14 10:33
 */
public class DijkstraAlgorithm2 {
    public static final double INFINITY = Double.POSITIVE_INFINITY;
    // 路网文件在resources下的路径
    public static final String OSM_PATH = "teng.osm";
    public static void main(String[] args) throws Exception {

        // 路网中所有点: OSM中所有顶点
        List<Node> nodeList = OsmUtil.getAllNode(OSM_PATH);

        // 路网中所有路: OSM中所有路
        List<Way> wayList = OsmUtil.getAllWay(OSM_PATH, nodeList);

        // 处理挖填方与路网数据之间的关系
        //handleOutIn(nodeList,wayList);

        // 处理障碍物(包括控制性工程)与路网数据的关系
        //handleHinder(nodeList, wayList);

        String beginId = "4034633263";
        String endId = "4143818359";
        BestRoad bestRoad = getBestRoadByDijkstra(beginId, endId, nodeList, wayList);
        System.out.println("最短距离: "+ bestRoad.getDist());
        System.out.println("路线: "+ bestRoad.getRoadNodeList());

        //System.out.println(bestRoad);
    }

    /**
     * 获取最短路线
     * @param beginId 开始点的路网ID 对应osm文件中 <node id='-102866' lat='29.7278756' lon='106.5759007' />中的ID
     * @param endId 终点的路网ID,同上
     * @param nodeList 路网所有顶点 osm中所有<node> 节点
     * @param wayList 路网所有路
     * @return 路线点集
     */
    public static BestRoad getBestRoadByDijkstra(String beginId,String endId,List<Node> nodeList, List<Way> wayList) {
        // 邻接矩阵,当前没有加挖方点和填方点,和障碍
        double[][] matrix = new double[nodeList.size()][nodeList.size()];

        // 将 wayList => double[][] matrix
        for (int i = 0; i < nodeList.size(); i++) {
            Node node1 = nodeList.get(i);
            for (int j = 0; j < nodeList.size(); j++) {
                Node node2 = nodeList.get(j);
                // 设置相邻矩阵中的每个位置的值
                matrix[i][j] = getDistanceBy2Point(node1,node2, wayList);

            }

        }

        //创建 Graph对象
        DGraph2 graph = new DGraph2(nodeList, matrix);
        //测试, 看看图的邻接矩阵是否ok
        //graph.showGraph();


        // 得到出发点下标
        int beginIndex = getIndexByValue(beginId, nodeList);
        //测试迪杰斯特拉算法
        graph.dijkstra(beginIndex);
        // 在路线方案中放去点,即可得到结果
        return graph.showDijkstra(nodeList, beginId, endId);

    }

    public static int getIndexByValue(String id,List<Node> nodeList) {
        for (int i = 0; i < nodeList.size(); i++) {
            if (nodeList.get(i).getId().equals(id)) {
                return i;
            }
        }
        return 0;
    }

    /**
     * 计算两点间的距离
     * @param node1 第一个点
     * @param node2 第二个点
     * @param wayList
     * @return
     */
    public static double getDistanceBy2Point(Node node1, Node node2,List<Way> wayList) {
        // 1. 判断两个点的id在wayList中是否相邻,相邻则计算距离,否则返回无穷大
        for (Way way : wayList) {
            // 当前路中的所有点
            List<Node> nodes = way.getNodes();

            // 判断 node1 是否在 way 中
            // 第一个点在way中的默认位置, -1表示不在way中
            int index1 = -1;
            for (int i = 0; i < nodes.size(); i++) {
                // 得到第一个点在way中的位置
                if (nodes.get(i).getId().equals(node1.getId())) {
                    // 赋值node1的位置,并结束遍历
                    index1 = i;
                    break;
                }
            }

            // node1 点不在way中,跳过
            if (index1 == -1) {
                continue;
            }
            
            // 判断index1的相邻点是否为node2,
            boolean adjoin = adjoin(node2, nodes, index1);
            if (adjoin) {
                // 计算两点距离
                double distance = DistanceUtils.getDistance(Double.valueOf(node1.getLon()), Double.valueOf(node1.getLat()), Double.valueOf(node2.getLon()), Double.valueOf(node2.getLat()));
                return distance;

            }

        }

        return INFINITY;
    }

    /**
     * 判断 nodes 中 与 index1 相邻的 值是否为 node2
     * @param node2 第二个顶点对象
     * @param nodes 道路所有中所有点
     * @param index1 nodes中的下标
     * @return
     */
    private static boolean adjoin(Node node2, List<Node> nodes, int index1) {
        boolean afterEq;
        boolean beforeEq;

        // 第一个点在0位置,判断后一个点是否为node2
        if (index1 == 0) {
            afterEq = nodes.get(index1 + 1).getId().equals(node2.getId());
            if (afterEq) {
                return true;
            }
        }

        // 第一个点不在两端点 ( 0 , nodes.size()-1 ),判断前后一个点是否为node2
        if (index1 > 0 && index1 < nodes.size() - 1) {
            beforeEq = nodes.get(index1 - 1).getId().equals(node2.getId());
            afterEq = nodes.get(index1 + 1).getId().equals(node2.getId());
            if (beforeEq || afterEq) {
                return true;
                
            }
        }

        // 第一个点在最后位置 nodes.size()-1,判断前一个点是否为ndoe2
        if (index1 == nodes.size() - 1) {
            beforeEq = nodes.get(index1 - 1).getId().equals(node2.getId());
            if (beforeEq) {
                return true;
                
            }
        }

        return false;
    }

}

//已访问顶点集合
class VisitedVertex2 {
    //记录各个顶点是否访问，1表示访问过，0表示未访问过
    public int[] alreadyVertex;
    //表示从源点到顶点i之间的最短路径的前驱结点
    public int[] path;
    //记录从源点到其他各个顶点当前的最短路径长度
    public double[] dist;

    /**
     * 构造器
     *
     * @param vertexNum   顶点数目
     * @param vertexIndex 顶点索引（顶点数组对应的下标）
     */
    public VisitedVertex2(int vertexNum, int vertexIndex) {
        this.alreadyVertex = new int[vertexNum];
        this.path = new int[vertexNum];
        this.dist = new double[vertexNum];

        //初始化dist数组，顶点i到其他顶点的距离初始为65536，到自己的距离初始为0。
        Arrays.fill(dist, DijkstraAlgorithm2.INFINITY);
        dist[vertexIndex] = 0;
        //初始顶点已访问
        this.alreadyVertex[vertexIndex] = 1;
    }

    /**
     * 判断该顶点是否已经访问过
     *
     * @param vertexIndex 顶点索引
     * @return
     */
    public boolean isVisited(int vertexIndex) {
        return alreadyVertex[vertexIndex] == 1;
    }

    /**
     * 更新源点到目标顶点的最短路径长度
     *
     * @param objectiveVertexIndex  目标顶点索引
     * @param objectiveVertexLength 目标顶点长度
     */
    public void updateDist(int objectiveVertexIndex, double objectiveVertexLength) {
        dist[objectiveVertexIndex] = objectiveVertexLength;
    }

    /**
     * 更新源点到该顶点最短路径下，该顶点的前驱顶点
     *
     * @param preVertexIndex 前驱顶点
     * @param VertexIndex    该顶点
     */
    public void updatePath(int VertexIndex, int preVertexIndex) {
        path[VertexIndex] = preVertexIndex;
    }

    /**
     * 返回源点到该顶点的上一次更新的最短路径
     * 用于判断此次是否更新最短路径长度
     *
     * @param vertexIndex
     * @return
     */
    public double getDist(int vertexIndex) {
        return dist[vertexIndex];
    }

    /**
     * 寻找与源点之间最短距离且未访问顶点的索引
     *
     * @return
     */
    public int updateArr() {
        double min = Double.POSITIVE_INFINITY;
        int index = 0;
        for (int i = 0; i < alreadyVertex.length; i++) {
            if (alreadyVertex[i] == 0 && dist[i] < min) {
                min = dist[i];
                index = i;
            }
        }
        alreadyVertex[index] = 1;
        return index;
    }

    public BestRoad show(List<Node> vertex,String beginId, String endId) {
        // 起点在所有顶点中的下标
        int beginIndex = 0;
        // 终点在所有顶点中的下标
        int endIndex = 0;
        //char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        for (int i = 0; i < vertex.size(); i++) {
            if (vertex.get(i).getId().equals(beginId)) {
                beginIndex = i;
            }
            if (vertex.get(i).getId().equals(endId)) {
                endIndex = i;
            }
        }
        BestRoad bestRoad = new BestRoad();
        // 最短距离
        bestRoad.setDist(dist[endIndex]);

        // 如果距离为无穷,表示没有路线
        if (bestRoad.getDist() == Double.POSITIVE_INFINITY) {
            return bestRoad;
        }

        // 设置路线
        List<Node> roadNodeList = new ArrayList<Node>();
        //System.out.println(beginId + " -> " + endId + "的最短距离为：" + dist[endIndex]);
        //System.out.print(beginId + " -> " + endId + "的最短路径为：");
        showPath(vertex,beginIndex, endIndex,roadNodeList);

        roadNodeList.add(vertex.get(endIndex));
        //System.out.println(vertex.get(endIndex).getId());
        //System.out.println(roadNodeList);
        // 路线点集
        bestRoad.setRoadNodeList(roadNodeList);

        return bestRoad;
    }

    /**
     * 通过递归遍历先驱数组path返回最短路径
     *
     * @param vertex 所有顶点
     * @param beginIndex
     * @param endIndex
     * @param roadNodeList 路线顶点
     */
    private void showPath(List<Node> vertex,int beginIndex, int endIndex,List<Node> roadNodeList) {
        //char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        if (path[endIndex] == beginIndex) {
            roadNodeList.add(vertex.get(beginIndex));
            //System.out.print(vertex.get(beginIndex).getId() + " -> ");
            return;
        } else {
            showPath(vertex,beginIndex, path[endIndex],roadNodeList);
        }
        roadNodeList.add(vertex.get(path[endIndex]));
        //System.out.print(vertex.get(path[endIndex]).getId() + " -> ");
    }

}

/**
 * 图对象
 */
class DGraph2 {

    //private char[] vertex;//顶点数组
    private List<Node> vertex;//顶点集合

    private double[][] arcs;//邻接矩阵
    private VisitedVertex2 visitedVertex;


    public DGraph2(List<Node> vertex, double[][] arcs) {
        this.vertex = vertex;
        this.arcs = arcs;
    }

    public void showGraph() {
        for (double[] link : arcs) {
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * dijkstra算法
     *
     * @param index 出发顶点的下标
     */
    public void dijkstra(int index) {
        visitedVertex = new VisitedVertex2(vertex.size(), index);
        update(index);
        for (int i = 1; i < vertex.size(); i++) {
            index = visitedVertex.updateArr();
            update(index);
        }

    }

    //更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
    public void update(int index) {
        double len = 0;
        //根据邻接矩阵找到邻接顶点
        for (int i = 0; i < arcs[index].length; i++) {
            //从出发顶点到index顶点的距离+ 从index顶点到i顶点的距离的和
            len = visitedVertex.getDist(index) + arcs[index][i];
            if (!visitedVertex.isVisited(i) && len < visitedVertex.getDist(i)) {
                visitedVertex.updatePath(i, index);//更新前驱顶点
                visitedVertex.updateDist(i, len); //更新最短距离
            }

        }

    }

    /**
     * 显示并返回最优路线序列
     * @param vertex 所有点
     * @param beginId 起点ID
     * @param endId 终点ID
     * @return
     */
    public BestRoad showDijkstra(List<Node> vertex,String beginId, String endId) {
        return visitedVertex.show(vertex, beginId, endId);
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/711018