Dijkstra求含权图最短通路；试探与回溯保证枚举的不遗漏不重复;国际象棋八皇后问题

求两节点的最短通路，对于无权图，可以通过图的广度优先遍历求解。含权图一般通过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中的节点（可能经历多个点的距离低于和直接相邻的点的距离）
Iterator  it=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);
}
}

原文：http://blog.csdn.net/needkane/article/details/25282669