首页 > Java > java教程 > Java实现Dijkstra输出最短路径的方法介绍

Java实现Dijkstra输出最短路径的方法介绍

黄舟
发布: 2017-09-23 09:52:47
原创
1996 人浏览过

这篇文章主要介绍了Java实现Dijkstra输出最短路径的实例的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下

Java实现Dijkstra输出指定起点到终点的最短路径

前言:

最近在公司参加了一个比赛,其中涉及的一个问题,可以简化成如是描述:一个二维矩阵,每个点都有权重,需要找出从指定起点到终点的最短路径。

马上就想到了Dijkstra算法,所以又重新温故了一遍,这里给出Java的实现。

而输出最短路径的时候,在网上也进行了查阅,没发现什么标准的方法,于是在下面的实现中,我给出了一种能够想到的比较精简的方式:利用prev[]数组进行递归输出。


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

package graph.dijsktra;

  

import graph.model.Point;

  

import java.util.*;

  

/**

 * Created by MHX on 2017/9/13.

 */

public class Dijkstra {

  private int[][] map; // 地图结构保存

  private int[][] edges; // 邻接矩阵

  private int[] prev; // 前驱节点标号

  private boolean[] s; // S集合中存放到起点已经算出最短路径的点

  private int[] dist; // dist[i]表示起点到第i个节点的最短路径

  private int pointNum; // 点的个数

  private Map<Integer, Point> indexPointMap; // 标号和点的对应关系

  private Map<Point, Integer> pointIndexMap; // 点和标号的对应关系

  private int v0; // 起点标号

  private Point startPoint; // 起点

  private Point endPoint; // 终点

  private Map<Point, Point> pointPointMap; // 保存点和权重的映射关系

  private List<Point> allPoints; // 保存所有点

  private int maxX; // x坐标的最大值

  private int maxY; // y坐标的最大值

  

  public Dijkstra(int map[][], Point startPoint, Point endPoint) {

    this.maxX = map.length;

    this.maxY = map[0].length;

    this.pointNum = maxX * maxY;

    this.map = map;

    this.startPoint = startPoint;

    this.endPoint = endPoint;

    init();

    dijkstra();

  }

  

  /**

   * 打印指定起点到终点的最短路径

   */

  public void printShortestPath() {

    printDijkstra(pointIndexMap.get(endPoint));

  }

  

  /**

   * 初始化dijkstra

   */

  private void init() {

    // 初始化所有变量

    edges = new int[pointNum][pointNum];

    prev = new int[pointNum];

    s = new boolean[pointNum];

    dist = new int[pointNum];

    indexPointMap = new HashMap<>();

    pointIndexMap = new HashMap<>();

    pointPointMap = new HashMap<>();

    allPoints = new ArrayList<>();

  

    // 将map二维数组中的所有点转换成自己的结构

    int count = 0;

    for (int x = 0; x < maxX; ++x) {

      for (int y = 0; y < maxY; ++y) {

        indexPointMap.put(count, new Point(x, y));

        pointIndexMap.put(new Point(x, y), count);

        count++;

        allPoints.add(new Point(x, y));

        pointPointMap.put(new Point(x, y), new Point(x, y, map[x][y]));

      }

    }

  

    // 初始化邻接矩阵

    for (int i = 0; i < pointNum; ++i) {

      for (int j = 0; j < pointNum; ++j) {

        if (i == j) {

          edges[i][j] = 0;

        } else {

          edges[i][j] = 9999;

        }

      }

    }

  

    // 根据map上的权重初始化edges,当然这种算法是没有单独加起点的权重的

    for (Point point : allPoints) {

      for (Point aroundPoint : getAroundPoints(point)) {

        edges[pointIndexMap.get(point)][pointIndexMap.get(aroundPoint)] = aroundPoint.getValue();

      }

    }

  

    v0 = pointIndexMap.get(startPoint);

  

    for (int i = 0; i < pointNum; ++i) {

      dist[i] = edges[v0][i];

      if (dist[i] == 9999) {

        // 如果从0点(起点)到i点最短路径是9999,即不可达

        // 则i节点的前驱节点不存在

        prev[i] = -1;

      } else {

        // 初始化i节点的前驱节点为起点,因为这个时候有最短路径的都是与起点直接相连的点

        prev[i] = v0;

      }

    }

  

    dist[v0] = 0;

    s[v0] = true;

  }

  

  /**

   * dijkstra核心算法

   */

  private void dijkstra() {

    for (int i = 1; i < pointNum; ++i) { // 此时有pointNum - 1个点在U集合中,需要循环pointNum - 1次

      int minDist = 9999;

      int u = v0;

  

      for (int j = 1; j < pointNum; ++j) { // 在U集合中,找到到起点最短距离的点

        if (!s[j] && dist[j] < minDist) { // 不在S集合,就是在U集合

          u = j;

          minDist = dist[j];

        }

      }

      s[u] = true; // 将这个点放入S集合

  

      for (int j = 1; j < pointNum; ++j) { // 以当前刚从U集合放入S集合的点u为基础,循环其可以到达的点

        if (!s[j] && edges[u][j] < 9999) {

          if (dist[u] + edges[u][j] < dist[j]) {

            dist[j] = dist[u] + edges[u][j];

            prev[j] = u;

          }

        }

      }

    }

  }

  

  private void printDijkstra(int endPointIndex) {

    if (endPointIndex == v0) {

      System.out.print(indexPointMap.get(v0) + ",");

      return;

    }

    printDijkstra(prev[endPointIndex]);

    System.out.print(indexPointMap.get(endPointIndex) + ",");

  }

  

  private List<Point> getAroundPoints(Point point) {

    List<Point> aroundPoints = new ArrayList<>();

    int x = point.getX();

    int y = point.getY();

    aroundPoints.add(pointPointMap.get(new Point(x - 1, y)));

    aroundPoints.add(pointPointMap.get(new Point(x, y + 1)));

    aroundPoints.add(pointPointMap.get(new Point(x + 1, y)));

    aroundPoints.add(pointPointMap.get(new Point(x, y - 1)));

    aroundPoints.removeAll(Collections.singleton(null)); // 剔除不在地图范围内的null点

    return aroundPoints;

  }

  

  public static void main(String[] args) {

    int map[][] = {

        {1, 2, 2, 2, 2, 2, 2},

        {1, 0, 2, 2, 0, 2, 2},

        {1, 2, 0, 2, 0, 2, 2},

        {1, 2, 2, 0, 2, 0, 2},

        {1, 2, 2, 2, 2, 2, 2},

        {1, 1, 1, 1, 1, 1, 1}

    }; // 每个点都代表权重,没有方向限制

    Point startPoint = new Point(0, 3); // 起点

    Point endPoint = new Point(5, 6); // 终点

    Dijkstra dijkstra = new Dijkstra(map, startPoint, endPoint);

    dijkstra.printShortestPath();

  }

}

登录后复制


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

package graph.model;

  

public class Point {

  private int x;

  private int y;

  private int value;

  

  public Point(int x, int y) {

    this.x = x;

    this.y = y;

  }

  

  public Point(int x, int y, int value) {

    this.x = x;

    this.y = y;

    this.value = value;

  }

  

  public int getX() {

    return x;

  }

  

  public void setX(int x) {

    this.x = x;

  }

  

  public int getY() {

    return y;

  }

  

  public void setY(int y) {

    this.y = y;

  }

  

  public int getValue() {

    return value;

  }

  

  public void setValue(int value) {

    this.value = value;

  }

  

  @Override

  public String toString() {

    return "{" +

        "x=" + x +

        ", y=" + y +

        &#39;}&#39;;

  }

  

  @Override

  public boolean equals(Object o) {

    if (this == o) return true;

    if (o == null || getClass() != o.getClass()) return false;

  

    Point point = (Point) o;

  

    if (x != point.x) return false;

    return y == point.y;

  }

  

  @Override

  public int hashCode() {

    int result = x;

    result = 31 * result + y;

    return result;

  }

}

登录后复制

以上是Java实现Dijkstra输出最短路径的方法介绍的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板