Dijkstra求含权图最短通路；试探与回溯保证枚举的不遗漏不重复

Dijkstra求含权图最短通路；试探与回溯保证枚举的不遗漏不重复2014-12-10 csdn博客 u010026901求两节点的最短通路，对于无权图，可以通过图的广度优先遍历求解。含权图一般通过Dijkstra算法求解。

import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.List;import java.util.Map;public class Shortest {static class Cell{int node;//连接到哪个节点int weight;//边的权值public Cell（int node,int weight）{this.node=node;this.weight=weight;}}@SuppressWarnings（"unchecked"）public static void main（String[] args） {List[] g=new List[11];for（int i=0;i<g.length;i++）g[i]=new ArrayList（）;//邻接表形式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=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中的节点（可能经历多个点的距离低于和直接相邻的点的距离）Iteratorit=map.keySet（）.iterator（）;while（it.hasNext（））{int k=（Integer）it.next（）;int w=（Integer）map.get（k）;//集合中的节点对应的最小路径值for（int i=0;i<g[k].size（）;i++）{Cell t=（Cell）g[k].get（i）;if（map.get（t.node）==null&&t.weight+w<min）{min_no=t.node;min=t.weight+w;}}}if（min<Integer.MAX_VALUE）{map.put（min_no,min）;}else{break;}}System.out.print（map）;}}

结果：{0=2, 1=3, 2=4, 3=5, 4=1, 5=3, 6=6, 7=5, 8=6, 9=7, 10=7} 0到本身的距离这里计算是按照到4，才从4回到0，所以等于2

所谓”遍历”或“枚举”即是要逐一列出所有情况。其要点是要满足两个要求：1不能重复；2不能遗漏。“不能重复”要求我们在遍历时要有章法，按照某种设计的路线来进行。试探与回溯是最为常用的、易于理解的设计思路。八皇后问题有多个解

public class NoAttack {/*** 八皇后问题，这里不需要用8*8的棋盘，必须每个皇后不在同一行，横竖可以攻击 同时不可以在对角线的位置，攻击距离不限*//*** 检验新皇后放入后，是否冲突*/static boolean check（int[] a, int row, int col） {for （int i = 0; i < row; i++） {// 纵向上是否冲突if （col == a[i]）return false;// 与先前皇后的列冲突// 对角线检验if （row - i == Math.abs（col - a[i]））return false;}return true;}static void show（int[] a）{for（int i=0;i<a.length;i++）{System.out.print（a[i]+" "）;}System.out.println（）;}/*** 对数组放置第K个皇后*/static void f（int[] a, int k） {if （k == 8） {show（a）;return;// 跳出递归}// 对8个位置逐一试探for （int i = 0; i < 8; i++） {a[k] = i;// 将第k个皇后放在第i个位置，进行检查if （check（a, k, i））f（a, k + 1）;}}public static void main（String[] args） {int[] a = new int[8];// 记录每行皇后的位置f（a, 0）;}}