用Java语言实现Dijkstra算法的一种简单直白的写法
（一）网络的图：
注：只考虑最简单的情况，无向图，各条边距离都为正整数大于0。原节点是A，需要计算从A到节点B、C、D、E、F、G的最短路径，不考虑跳数。
该图可以用下面的矩阵来表示：
int[][] juzhen = {
// /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
/*A*/ { 0, 12, INF, INF, INF, 16, 14},
/*B*/ { 12, 0, 10, INF, INF, 7, INF},
/*C*/ { INF, 10, 0, 3, 5, 6, INF},
/*D*/ { INF, INF, 3, 0, 4, INF, INF},
/*E*/ { INF, INF, 5, 4, 0, 2, 8},
/*F*/ { 16, 7, 6, INF, 2, 0, 9},
/*G*/ { 14, INF, INF, INF, 8, 9, 0}
};
（二）设计节点类：
//节点类；
class Node{
//上一个节点；
Node prev;
//节点字母名称；
String name;
//矩阵中的节点编号；
int bianhao;
//计算出的起始点到此节点的最短距离；
int zuiduanjuli;
//计算出的从原点到此的具体路径；
ArrayList<Node> LUJING = new ArrayList<Node>();
//构造器；
Node(String name,int bianhao){
this.name = name;
this.bianhao = bianhao;
}
}
//初始化节点：
//初始化起始节点：
Node A = new Node("A",0);
A.zuiduanjuli = 0;
//初始化其他节点；
Node B = new Node("B",1);
Node C = new Node("C",2);
Node D = new Node("D",3);
Node E = new Node("E",4);
Node F = new Node("F",5);
Node G = new Node("G",6);
（三）设计两个节点集合：
首先设计一个还未计算出最短路径的集合的节点，设为N，该集合初始化为包含节点B、C、D、E、F、G。
其次设计一个已经计算出最短路径的节点的集合，设为N'。该集合初始化为只有原节点A。
//初始化两个集合：
//初始化还未算出最短路径的节点集合N；
ArrayList<Node> N = new ArrayList<Node>();
N.add(B);
N.add(C);
N.add(D);
N.add(E);
N.add(F);
N.add(G);
//初始化已算出最短路径的节点集合N1；
ArrayList<Node> N1 = new ArrayList<Node>();
N1.add(A);
（四）具体计算过程：
最外层循环：集合N中有多少个节点，就迭代多少次。每次迭代计算出N中拥有最短路径的节点，将此节点从集合N中删除，加入到集合N'。最后直到集合N变空。
核心思路是：每次最内层循环计算只计算1跳，穷举N中的每个节点到N'中的每个节点的一跳的距离,设为 “ yitiao ”。总共需要两层内层迭代，总共计算 “ N.size() X N'.size() ”次，每一个 “ yitiao ”再加上其上一个节点（在集合N'中）已经算出的 “ node.zuiduanjuli ”，其和设为“ 本次距离 ”： “ bencijuli ”。在所有 “ N.size() X N'.size() ”个“ bencijuli ”中，最小值即为本次迭代中选出的最短路径，其对应节点被选出，加入集合N1中。
至于为什么只计算“ 一跳 ”的本次迭代算出的最小“ bencijuli ”为该被选出节点的最短路径，是因为“ 一跳里边最小的，一定小于2跳或更多跳 ”。考虑该“ 2跳或更多跳 ”到本次迭代选出被选出的节点的整个路径，其整个路径中必定包含有一跳是从集合N'中的一节点到集合N中的一节点，否则无法联通集合N'和集合N。而“ 截止到包含这一跳的总路径的距离 ”一定大于或等于计算出的最小“ bencijuli "，从而整个路径一定大于或等于选出的最小“ bencijuli "。如图：
（五）打印输出结果：
将节点类内部字段的路径：ArrayList<Node> LUJING 打印出来：
以下是具体代码：
import java.util.ArrayList;
public class Dijkstra {
//节点类；
static class Node{
//上一个节点；
Node prev;
//节点字母名称；
String name;
//矩阵中的节点编号；
int bianhao;
//计算出的起始点到此节点的最短距离；
int zuiduanjuli;
//计算出的从原点到此的具体路径；
ArrayList<Node> LUJING = new ArrayList<Node>();
//构造器；
Node(String name,int bianhao){
this.name = name;
this.bianhao = bianhao;
}
}
public static void main(String[] args) {
//初始化；
//初始化矩阵：
final int INF = Integer.MAX_VALUE;
int[][] juzhen = {
// /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
/*A*/ { 0, 12, INF, INF, INF, 16, 14},
/*B*/ { 12, 0, 10, INF, INF, 7, INF},
/*C*/ { INF, 10, 0, 3, 5, 6, INF},
/*D*/ { INF, INF, 3, 0, 4, INF, INF},
/*E*/ { INF, INF, 5, 4, 0, 2, 8},
/*F*/ { 16, 7, 6, INF, 2, 0, 9},
/*G*/ { 14, INF, INF, INF, 8, 9, 0}
};
//初始化节点；
//初始化起始节点：
Node A = new Node("A",0);
A.zuiduanjuli = 0;
//初始化其他节点：
Node B = new Node("B",1);
Node C = new Node("C",2);
Node D = new Node("D",3);
Node E = new Node("E",4);
Node F = new Node("F",5);
Node G = new Node("G",6);
//初始化两个集合；
//初始化还未算出最短路径的节点集合N：
ArrayList<Node> N = new ArrayList<Node>();
N.add(B);
N.add(C);
N.add(D);
N.add(E);
N.add(F);
N.add(G);
//初始化已算出最短路径的节点集合N1：
ArrayList<Node> N1 = new ArrayList<Node>();
N1.add(A);
//迭代：
//最外层循环，一共7个节点，故整个算法一共需要迭代6次，每次算出一个最短节点，加入N1中；
for(int i = 0; i < 6; i++){
//每次迭代算出的最短路径长度；
int min = INF;
//每次迭代算出的最短节点；
Node node = null;
//第二层循环，对N1中每一个元素进行一次迭代；
for(int p = 0;p < N1.size();p++){
//当前的N1内的节点；
Node nowN1= N1.get(p);
//第三层循环，对N中每一个元素进行一次迭代；
for(int q = 0;q < N.size();q++){
//当前的N内的节点；
Node nowN= N.get(q);
//两点间一跳的距离；
int yitiao = juzhen[nowN1.bianhao][nowN.bianhao];
//选择更新；
if(yitiao != INF){
//本次距离；
int bencijuli = nowN1.zuiduanjuli + yitiao;
if (bencijuli < min){
//更新最小值；
min = bencijuli;
//更新待加入N1的节点；
node = nowN;
node.zuiduanjuli = min;
node.prev = nowN1;
node.LUJING.clear();
node.LUJING.addAll(nowN1.LUJING);
node.LUJING.add(nowN);
}
}
}
}
//回到最外层循环，更新选出的节点字段;
node.zuiduanjuli = min;
//更新集合N和N1；
N.remove(node);
N1.add(node);
}
//打印输出结果；
for(int i = 1;i < N1.size();i++){
//取出本次的路径经过的节点数；
int size = N1.get(i).LUJING.size();
//取出本次的具体路径；
ArrayList<Node> BENCILUJING = N1.get(i).LUJING;
//打印最短距离；
System.out.println("节点：" + N1.get(i).name + " 最短距离 : " + N1.get(i).zuiduanjuli);
//打印具体路径；
System.out.print("路径：A → ");
for(int j = 0;j < size-1;j++) {
System.out.print(BENCILUJING.get(j).name + " → ");
}
System.out.println(N1.get(i).name);
System.out.println();
}
}
}
以下是运行后的输出结果；
节点：B 最短距离 : 12
路径：A → B
节点：G 最短距离 : 14
路径：A → G
节点：F 最短距离 : 16
路径：A → F
节点：E 最短距离 : 18
路径：A → F → E
节点：C 最短距离 : 22
路径：A → B → C
节点：D 最短距离 : 22
路径：A → F → E → D