迪杰斯特拉算法主要是用广度优先搜索的算法计算出一个顶点V到各个顶点的最短距离
ver表示没有走过的顶点，dis表示顶点V到各个顶点的距离
首先从ver集合取出取出顶点M，将顶点V的相邻顶点之间的边取出，存储在一个list1集合里面，将其排序
从list1集合取出最小值的顶点N，并查看VM加上MN的距离是否小于VN的距离，小于则更新，并且从未走的集合中删除顶点N
public class DijkstraTest {
public static void main(String[] args) {
int INF = Integer.MAX_VALUE;
char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
int[][] edges = {
{0, 12, INF, INF, INF, 16, 14 },
{12, 0, 10, INF, INF, 7, INF },
{INF, 10, 0, 3, 5, 6, INF },
{INF, INF, 3, 0, 4, INF,INF },
{INF, INF, 5, 4, 0, 2, 8 },
{16, 7, 6, INF, 2, 0, 9 },
{14, INF, INF, INF, 8, 9, 0 },
};
Dijkstra dijkstra = new Dijkstra(vertexs,edges);
dijkstra.getMinTrace('C');
dijkstra.showMinTrace();
}
}
class Dijkstra{
private char[] vertexs; //顶点集合
private int[] dist; //目标点到各个点的最短距离
private int[][] edges; //邻接矩阵
private ArrayList<MData> firstList; //因为迪杰斯特拉采用广度优先搜索遍历，所以这个存放第一层需要遍历的点的信息
private ArrayList<MData> secondList; //在将firstList中取出一个点查看他的邻接点的时候，会查看我们的出发点到当前顶点的距离是否小于出发点到该顶点邻接点的最小距离，如果是，则加入secondList集合，并且更新出发点到该邻接点的最小距离
private HashSet<Character> choice; //没有走过的顶点
private static final int INF = Integer.MAX_VALUE;
private HashMap<Character,Integer> vertexToIndex; //将字符转换成其索引，为了方便
private int startIndex; //出发点在顶点中的索引
public Dijkstra(char[] vertexs, int[][] edges) { //初始化工作
this.vertexs = vertexs;
this.edges = edges;
vertexToIndex = new HashMap<>();
choice = new HashSet<>();
for (int i = 0; i < vertexs.length; i++) {
vertexToIndex.put(vertexs[i],i);
choice.add(vertexs[i]);
}
firstList = new ArrayList();
}
public void getMinTrace(char start){ //基本上也是初始化工作
startIndex = vertexToIndex.get(start);
dist = new int[vertexs.length];
for (int i = 0; i < dist.length; i++) { //首先将出发点到各个顶点的距离设置未无穷大
dist[i] = INF;
}
firstList.add(new MData(start,0)); // 首先加入出发点，便于后面遍历
dist[startIndex] = 0; //设置自身距离为0
choice.remove(start); //将出发点从没有走过的顶点里面进行删除
getMinTrace(); //调用核心算法
}
public void getMinTrace(){
while (!choice.isEmpty()){ //还有点没有走完就继续
secondList = new ArrayList(); //每一轮都需要从新new一下
while (!firstList.isEmpty()){ //进行这一层的遍历，因为这里面遍历需要从小打到的遍历，不然就可以直接将firstList与secondList合并为一个了
MData temp = firstList.remove(0); // 取出删除
int tempIndex = vertexToIndex.get(temp.next); //获取 当前点的索引
for (int i = 0; i < edges.length; i++) { //遍历该顶点的邻接点了
//temp.weight表示当前遍历点到中心点的最小距离，edges[tempIndex][i]表示改变里点到邻接点的距离，dist[i]表示在这之前中心点到该邻接点的最小距离
if(temp.weight + edges[tempIndex][i] < dist[i] && temp.weight + edges[tempIndex][i] > 0){
dist[i] = temp.weight + edges[tempIndex][i];
secondList.add(new MData(vertexs[i],dist[i]));
choice.remove(vertexs[i]);
}
}
}
Collections.sort(secondList); //取出来的时候需要从小到大取出，所以需要先进性排序
firstList = secondList; //赋值进行下一轮遍历
}
}
public void showMinTrace(){
System.out.println(Arrays.toString(dist));
}
}
class MData implements Comparable<MData> {
public char next; //需要从这个点去探索邻接点
public int weight; //当前（在每一轮循环中）出发点到这个点的最小距离
public MData(char next, int weight) {
this.next = next;
this.weight = weight;
}
public int compareTo(MData o) {
return weight - o.weight;
}
@Override
public String toString() {
return "MData{next=" + next + ", weight=" + weight + '}';
}
}
