单源最短路径算法,用于计算一个节点到其他所有节点的最短路径;java代码实现

import java.util.ArrayList;

public class Dijkstra{
static ArrayList<Side> map = null;

static ArrayList<Integer> redAgg = null;

static ArrayList<Integer> blueAgg = null;

static Side[] parents = null;

public static void main(String[] args){
// 初始化顶点集
int[] nodes = { 0, 1, 3, 2, 4, 5,6 };

// 初始化有向权重图
map = new ArrayList<Side>();
map.add(new Side(0, 1, 10));
map.add(new Side(0, 3, 30));
map.add(new Side(0, 4, 100));
map.add(new Side(1, 2, 50));
map.add(new Side(2, 4, 10));
map.add(new Side(3, 2, 20));
map.add(new Side(3, 4, 60));
map.add(new Side(4, 5, 50));
map.add(new Side(3, 5, 60));
map.add(new Side(5, 6, 10));
map.add(new Side(3, 6, 80));

// 初始化已知最短路径的顶点集，即红点集，只加入顶点0
redAgg = new ArrayList<Integer>();
redAgg.add(nodes[0]);

// 初始化未知最短路径的顶点集,即蓝点集
blueAgg = new ArrayList<Integer>();
for (int i = 1; i < nodes.length; i++)
blueAgg.add(nodes[i]);

// 初始化每个顶点在最短路径中的父结点,及它们之间的权重,权重-1表示无连通
parents = new Side[nodes.length];
parents[0] = new Side(-1, nodes[0], 0);
for (int i = 0; i < blueAgg.size(); i++) {
int n = blueAgg.get(i);
parents[i + 1] = new Side(nodes[0], n, getWeight(nodes[0], n));
}

// 找从蓝点集中找出权重最小的那个顶点,并把它加入到红点集中
while (blueAgg.size() > 0){
MinShortPath msp = getMinSideNode();
if(msp.getWeight()==-1)
msp.outputPath(nodes[0]);
else
msp.outputPath();

int node = msp.getLastNode();
redAgg.add(node);
// 如果因为加入了新的顶点,而导致蓝点集中的顶点的最短路径减小,则要重要设置
setWeight(node);
}

}

/** *//**
* 得到一个节点的父节点
*
* @param parents
* @param node
* @return
*/
public static int getParent(Side[] parents, int node) {
if (parents != null) {
for (Side nd : parents) {
if (nd.getNode() == node) {
return nd.getPreNode();
}
}
}
return -1;
}

/** *//**
* 重新设置蓝点集中剩余节点的最短路径长度
*
* @param preNode
* @param map
* @param blueAgg
*/
public static void setWeight(int preNode) {
if (map != null && parents != null && blueAgg != null) {
for (int node : blueAgg) {