import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.Map; /**迪杰斯特拉解法求最短路径*/ public class ExampleNearest { //定义内部类Cell,方便邻接表的表示 static class Cell { int node; // 连接到哪个节点 int weight; // 边的权值 public Cell(int node, int weight) { this.node = node; this.weight = weight; } } // 已找到的最短路径信息 @SuppressWarnings({ "unchecked", "rawtypes" }) public static void main(String[] args) { List[] g = new List[11];//使用邻接表的方式,有11个节点 for (int i = 0; i < g.length; i++){ g[i] = new ArrayList();//创建含有11个元素的数组,每个数组都是一个链表 } g[0].add(new Cell(1, 3));//对每一个邻接表,添加边 g[0].add(new Cell(4, 1));//包含节点和权值 g[1].add(new Cell(2, 1)); g[1].add(new Cell(6, 3)); g[1].add(new Cell(9, 4)); g[1].add(new Cell(5, 5)); g[1].add(new Cell(0, 3)); g[2].add(new Cell(1, 1)); g[2].add(new Cell(3, 1)); g[2].add(new Cell(6, 7)); g[3].add(new Cell(2, 1)); g[3].add(new Cell(10, 2)); g[4].add(new Cell(0, 1)); g[4].add(new Cell(5, 2)); g[5].add(new Cell(4, 2)); g[5].add(new Cell(1, 5)); g[5].add(new Cell(7, 2)); g[5].add(new Cell(8, 3)); g[6].add(new Cell(2, 3)); g[6].add(new Cell(3, 7)); g[6].add(new Cell(8, 2)); g[6].add(new Cell(10, 1)); g[7].add(new Cell(5, 2)); g[8].add(new Cell(5, 3)); g[8].add(new Cell(6, 2)); g[9].add(new Cell(1, 4)); g[9].add(new Cell(10, 2)); g[10].add(new Cell(3, 2)); g[10].add(new Cell(6, 1)); g[10].add(new Cell(9, 2)); // 求0号节点开始的所有最小路径 //迪杰斯特拉解法 //先建立一个集合,集合里包含当前已经找到的最小路径 //下面用Map表示上述集合,Map的Key是不能重复的 Map map = new HashMap(); // 节点号 ---> 最小路径值 while (true) { int min = Integer.MAX_VALUE; // 最小路径值 int min_no = -1; // 对应的节点号 //先去寻找所有与0号节点邻接,并且不在Map中的 for (int i = 0; i < g[0].size(); i++) { Cell t = (Cell) g[0].get(i); if (map.get(t.node) == null && t.weight < min) { min_no = t.node; min = t.weight; } } //与map中邻接的所有不在map中的点 Iterator it = map.keySet().iterator();//枚举map,调用map的键集keySet,调用iterator方法,取得枚举器 while (it.hasNext()) {//调用hasNext int k = (Integer) it.next();//调用next,枚举该map中的每一个键,k为已经找到的节点号 int v = (Integer) map.get(k); // 集合中的节点对应的最小路径值 //对每一个这样的节点号去寻找这样的邻接点,记录在个g[k]这个数组元素中 for (int i = 0; i < g[k].size(); i++) { Cell t = (Cell) g[k].get(i);//找到每一个邻接点,并把它设为t if (map.get(t.node) == null && t.weight + v < min) {//该点的权值加最小路径值v,若小于min,则认为找到了新的最小值的候选人 min_no = t.node; min = t.weight + v; } } } if (min < Integer.MAX_VALUE)//找到了候选人 map.put(min_no, min);//候选人加入map中 else break; } System.out.println(map); } }
最短路径-迪杰斯特拉解法-Dijkstra法,布布扣,bubuko.com
原文:http://blog.csdn.net/u011925500/article/details/20226601