# Dijkstra最短路径算法浅析及java实现

1. 如果
2. 要表示从图

### Dijkstra算法步骤：

1. 集合
2. 集合
3. 集合

1.

#### Java实现

// 图数据结构
public class Graph {
private int vertex_num;

private Vertex[] vertices;

public Graph(int vertex_num) {
this.vertex_num = vertex_num;
this.vertices = new Vertex[vertex_num];
for (int i = 0; i < vertex_num; i++) {
this.vertices[i] = new Vertex();
}
}

public int getVertex_num() {
return vertex_num;
}

public void setVertex_num(int vertex_num) {
this.vertex_num = vertex_num;
}

}

}

public Vertex[] getVertices() {
return vertices;
}

public void setVertices(Vertex[] vertices) {
this.vertices = vertices;
}
}
// 顶点数据结构
public class Vertex {

private int preIndex = -1;

private double dist = Double.MAX_VALUE;

private boolean isSelected = false;

public double getDist() {
return dist;
}

public void setDist(double dist) {
this.dist = dist;
}

public boolean isSelected() {
return isSelected;
}

public void setSelected(boolean selected) {
isSelected = selected;
}

public int getPreIndex() {
return preIndex;
}

public void setPreIndex(int preIndex) {
this.preIndex = preIndex;
}
}
// 算法实现
public class Dijkstra {

public static Graph calMinimumPath(Graph g, int startIndex) {

//init
for (int i = 0; i < g.getVertex_num(); i++) {
if (i == startIndex) {
g.getVertices()[i].setDist(0);
g.getVertices()[i].setPreIndex(-1);
// 将起点加入集合A
g.getVertices()[i].setSelected(true);
continue;
} else {
g.getVertices()[i].setPreIndex(startIndex);
}
}
}

for (int i = 0; i < g.getVertex_num(); i++) {
// 从备选集合B中选择一个点加入集合A
double min = Double.MAX_VALUE;
int selected = Integer.MAX_VALUE;
for (int j = 0; j < g.getVertex_num(); j++) {
if (!g.getVertices()[j].isSelected() && g.getVertices()[j].getDist() < min) {
selected = j;
min = g.getVertices()[j].getDist();
}
}
if (Double.MAX_VALUE == min) return g;
// 将被选中的点加入集合A
g.getVertices()[selected].setSelected(true);

for (int k = 0; k < g.getVertex_num(); k++) {
// 观察与被选中点S邻接的点R到目标点P的距离与R先到S再到P的距离的大小, 用小的替换
if (!g.getVertices()[k].isSelected() && g.getAdjacent_array()[k][selected] < Double.MAX_VALUE) {

if (g.getAdjacent_array()[k][selected] + g.getVertices()[selected].getDist() < g.getVertices()[k].getDist()) {
// 说明加入点S之后R到P的距离比之前更近,需更新R点到P点的路径和距离. 该步骤也将集合C中与S邻接的点移入了集合B中
g.getVertices()[k].setPreIndex(selected);
}
}
}
}
return g;
}

}
// 程序入口
public class MinimumPath {
public static void main(String[] args) {
int startIndex = 0;
Graph g = new Graph(5);
g.setAdjacent_array(new double[][]{{0, 100, 30, Double.MAX_VALUE, 10},
{100, 0, 60, 10, Double.MAX_VALUE},
{30, 60, 0, 60, Double.MAX_VALUE},
{Double.MAX_VALUE, 10, 60, 0, 50},
{10, Double.MAX_VALUE, Double.MAX_VALUE, 50, 0}});
g = Dijkstra.calMinimumPath(g, startIndex);
for (int i = 0; i < g.getVertex_num(); i++) {
int current = i;
while (g.getVertices()[current].getPreIndex() != -1) {
System.out.print(current + " -> ");
current = g.getVertices()[current].getPreIndex();
}
System.out.println(startIndex + " length: " + g.getVertices()[i].getDist());
}
}
}

0 length: 0.0
1 -> 3 -> 4 -> 0 length: 70.0
2 -> 0 length: 30.0
3 -> 4 -> 0 length: 60.0
4 -> 0 length: 10.0