Dijkstra算法java实现

import java.util.ArrayList; public class DijkstraDemo{ static ArrayList<Side> mapl = new ArrayList<Side>();//初始化图形数组 static ArrayList<Integer> redAgg = new ArrayList<Integer>();//初始化红色节点数组 static ArrayList<Integer> blueAgg = new ArrayList<Integer>();//初始化蓝色节点数组 static Side[] parents = null;//初始化有向边数组 public static void main(String[] args){ // 初始化顶点集 int[] nodes ={ 0, 1, 3, 7, 9}; // 初始化有向权重图 //mapl = new ArrayList<Side>(); //初始化数组 之前定义了数组类型 但是还要初始化数组 // mapl.add(new Side(0, 1, 10)); mapl.add(new Side(0, 3, 30)); // mapl.add(new Side(0, 4, 100)); // mapl.add(new Side(1, 2, 50)); // mapl.add(new Side(2, 4, 10)); // mapl.add(new Side(3, 2, 20)); // mapl.add(new Side(3, 4, 60)); // mapl.add(new Side(4, 5, 50)); // mapl.add(new Side(3, 5, 60)); // mapl.add(new Side(5, 6, 10)); // mapl.add(new Side(3, 6, 80)); // mapl.add(new Side(3, 8, 80)); mapl.add(new Side(3, 9, 80)); // mapl.add(new Side(8, 7, 10)); mapl.add(new Side(9, 7, 20)); // 初始化已知最短路径的顶点集，即红点集，初始的时候只加入顶点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的数组 长度为所有节点的个数 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)); //parents数组中保存的是有向边 初始的情况下所有前驱结点为0 没有边的时候 权值暂时为-1 } 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); //重新设置剩下的蓝点 一旦因为新的红点加入而使得路径变短，则将这次加入的红点设置为自己的父亲节点 } } /* * 得到一个节点的父节点 */ public static int getParent(Side[] parents, int node){ //parents数组中保存的是有向边 所有前驱结点为0的有向边 没有边的时候 权值为-1 if (parents != null){ for (Side nd : parents){ //对parents里边的每一条有向边 if (nd.getNode() == node){ //这里的node为要寻找父亲节点的当前节点 return nd.getPreNode(); } } } return -1; } /* * 重新设置蓝点集中剩余节点的最短路径长度 */ public static void setWeight(int preNode){ if (mapl != null && parents != null && blueAgg != null){ for (int node : blueAgg){ MinShortPath msp=getMinPath(node); //对每一个蓝点集中的节点，求出到到红点集中的初始源节点的最短路径 int w1 = msp.getWeight(); //w1指的是最短路径的权值总和 if (w1 == -1) continue; for (Side n : parents){ if (n.getNode() == node){ if (n.getWeight() == -1 || n.getWeight() > w1){ // n.setWeight(w1); //这里的n.getWeight是指从源节点到当前节点目前能找到的最短路径的权值 n.setPreNode(preNode);//重新设蓝点集中的点的父亲节点，将这一次找到的父亲节点（刚刚加入红点集的这个节点）作为当前节点的父亲节点 break; } } } } } } /* * 得到两点节点之间的权重 */ public static int getWeight(int preNode, int node){ if (mapl != null){ for (Side s : mapl){ //for each 语句 if (s.getPreNode() == preNode && s.getNode() == node) return s.getWeight(); } } return -1; } /* * 从蓝点集合中找出从源节点到本身的路径权值最小的那个节点 通过另外一个算法算出最短路径权值 这个类负责比较这些权值 找出最小的那个 */ public static MinShortPath getMinSideNode() { MinShortPath minMsp = null; if (blueAgg.size() > 0) { boolean a=false; int index = 0; for (int j = 0; j < blueAgg.size(); j++) { //对当前蓝点集中的每一个节点 MinShortPath msp = getMinPath(blueAgg.get(j)); //找到到这一轮可到达的蓝点集中每个节点的最短路径 if(msp.getWeight()==-1){ continue; } if (minMsp == null || msp.getWeight()!=-1 && msp.getWeight() < minMsp.getWeight()) { minMsp = msp; //存在找到了最短路径的蓝点并且现有的路径比后来的蓝点的路径权值要长 则将后来的蓝点路径赋值给当前最短路径 index = j; a=true; } } if(a){ blueAgg.remove(index); //从蓝点集中移除该蓝点 } else{ for (int j = 0; j < blueAgg.size(); j++) { //对当前蓝点集中的每一个节点 MinShortPath msp = getMinPath(blueAgg.get(j)); //找到到这一轮可到达的蓝点集中每个节点的最短路径 if (minMsp == null || msp.getWeight()!=-1 && msp.getWeight() < minMsp.getWeight()) { minMsp = msp; //存在找到了最短路径的蓝点并且现有的路径比后来的蓝点的路径权值要长 则将后来的蓝点路径赋值给当前最短路径 index = j; } } blueAgg.remove(index); } } return minMsp; } /* * 到某一节点的最短路径(实际上可能有多条,现在只考虑一条)————————这一轮可到达的蓝点 */ public static MinShortPath getMinPath(int node) { //这里的node为目的节点 遍历为蓝点集中的节点 MinShortPath msp = new MinShortPath(node); //定义一条目的为node节点的新最短路径 if (parents != null && redAgg != null) { for (int i = 0; i < redAgg.size(); i++) { MinShortPath tempMsp = new MinShortPath(node); //定义一条目的为node节点的新最短路径 该路径为不断变化的中间路径 int parent = redAgg.get(i); //将红点集中的节点依次取作前驱节点 int curNode = node; //蓝点集中的目的节点为当前节点 while (parent > -1) { //只要当前节点的前驱存在 int weight = getWeight(parent, curNode); //一旦选定的红点与当前节点之间有路径 if (weight > -1) { //红点集中的当前前驱节点与当前节点之间是连通的 tempMsp.addNode(parent); //则将这个前驱节点加入到最短路径的最前边 tempMsp.addWeight(weight); curNode = parent; //将前驱节点作为当前节点继续寻找 parent = getParent(parents, parent); //找到前驱节点的父亲节点 } else break; } if (msp.getWeight() == -1 || tempMsp.getWeight()!=-1 && msp.getWeight() > tempMsp.getWeight()) //如果找到路径 并且找到新的路径比原路径权值要小的时候，把新的路径赋值给，最短路径路径