回复 楼主 a287154777
程序代码：
public class Graph {
private Vertex[] vertexs;
private int[][] adjMat;
private int length = 0;
static final int INFINITY = ~(1 << 31); // 整数的最大值，表示没有路径
Graph(int size) { // 初始化
vertexs = new Vertex[size];
adjMat = new int[size][size];
for (int i = 0; i < size; i++)
// 将邻接矩阵初始化为全部不通
for (int j = 0; j < size; j++)
adjMat[i][j] = INFINITY;
}
public static void main(String[] args) {
Graph g = new Graph(36);
int x[][]={
{0,3,2,6,2,1},
{2,1,7,2,5,3},
{1,6,3,3,2,4},
{1,1,5,7,3,1},
{1,9,9,8,2,5},
{1,9,2,9,2,0}};
// 添加节点
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
StringBuilder sb=new StringBuilder();
sb.append("[").append(i).append(",").append(j).append("](").append(x[i][j]).append(")");
g.add(sb.toString());
}
}
// 添加有向有权边
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
int vx=i-1,vy=j-1;
while(vy<=j+1 && vy<6){
if(vx<0 || vy<0 || vx>=6 || (vx==i && vy==j)){
}else{
g.connect(i*6+j, vx*6+vy, x[vx][vy]);
}
vx++;
if(vx>i+1 || vx>=6){
vx=i-1;
vy++;
}
}
}
}
Path p = g.path(0); // 获得最小路径
p.print(); // 打印
}
void add(Object value) { // 添加顶点
assert length <= vertexs.length;
vertexs[length++] = new Vertex(value);
}
void connect(int from, int to, int length) {
adjMat[from][to] = length; // 设置指定节点之间的有向路径
}
/**
* 在邻接矩阵中，查找指定顶点的未访问过邻居顶点 如果从从起点到终点的边存在，且没有标志为访问，则返回终点下标。
*
* @param offset
* 指定开始查找的列
* @param index
* 指定查找的行
*/
int findNeighbor(int index, int offset) {
for (int i = offset; i < length; i++) {
if (adjMat[index][i] != INFINITY && !vertexs[i].isVisited())
return i;
}
return -1;
}
Vertex get(int index) {
return vertexs[index];
}
Path path(int index) { // 最小路径算法
assert vertexs[index] != null;
Path result = new Path(length, index, this); // 初始化Path
vertexs[index].visit(); // 将其实节点标志为访问过
for (int n = 1; n < length; n++) { // 一共经过n此迭代就可得到最终结果
int i = -1;
while ((i = findNeighbor(index, i + 1)) != -1)
// 寻找当前节点的所有为访问邻居
result.adjust(index, i, adjMat[index][i]); // 根据新路线调整最小路径
index = result.getMin(); // 将当前节点更新为路径表中为访问的最近的那个节点
vertexs[index].visit(); // 将当前节点标志为访问过;
}
clean();
return result;
}
boolean isVisited(int index) {
return vertexs[index].isVisited();
}
void clean() {
for (Vertex v : vertexs)
if (v != null)
v.clean();
}
}
class ParentLength { // 记载上一个节点与当前最小路径
private int parent; // 上一个节点
private int length; // 最小路径长度
ParentLength(int parent, int length) {
this.parent = parent;
this.length = length;
}
int parent() {
return parent;
}
int length() {
return length;
}
}
class Path { // 存储最小路径
private ParentLength[] pls;
private Graph g; // 确定指定位置的节点是否被访问过和打印时使用
Path(int size, int start, Graph g) {
// 初始化最小路径数组，将所有最小路径的起点都置为start，并将路径长度置为INFINITY
pls = new ParentLength[size];
for (int i = 0; i < size; i++)
pls[i] = new ParentLength(start, Graph.INFINITY);
this.g = g;
}
// 根据新发现的路径调整最小路径
void adjust(int from, int to, int length) {
// 根据上一个节点的路径，计算出新的路径长度
int newLength = pls[from].length() != Graph.INFINITY ? pls[from]
.length() + length : length;
// 如果到指定节点的新路径长度小于原来的最小路径，则更新到该节点的最小路径，和其父节点
if (newLength < pls[to].length())
pls[to] = new ParentLength(from, newLength);
}
int getMin() { // 求得到当前所有未访问节点的最近的一个节点
int pos = 0;
for (int i = 1; i < pls.length; i++)
if (!g.isVisited(i) && pls[i].length() < pls[pos].length())
pos = i;
return pos;
}
void print() { // 打印
for (int i = 0; i < pls.length; i++) {
int current = i;
System.out
.print((pls[current].length() == Graph.INFINITY ? "INFINITY"
: pls[current].length())
+ " ");
do {
System.out.print(g.get(current) + " <-- ");
current = pls[current].parent();
} while (current != pls[current].parent());
System.out.println(g.get(current));
}
}
}
class Vertex { // 顶点,记载数据value，并记载是否访问过
private Object value;
private boolean isVisited;
Vertex(Object value) {
this.value = value;
}
void visit() {
isVisited = true;
}
void clean() {
isVisited = false;
}
boolean isVisited() {
return isVisited;
}
Object value() {
return value;
}
@Override
public String toString() {
return "" + value;
}
}
INFINITY
[0,0](0) <-- [0,0](0)
3
[0,1](3) <-- [0,0](0)
3
[0,2](2) <-- [1,1](1) <-- [0,0](0)
9
[0,3](6) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
7
[0,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
8
[0,5](1) <-- [0,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
2
[1,0](2) <-- [0,0](0)
1
[1,1](1) <-- [0,0](0)
8
[1,2](7) <-- [1,1](1) <-- [0,0](0)
5
[1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
10
[1,4](5) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
10
[1,5](3) <-- [0,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
2
[2,0](1) <-- [1,1](1) <-- [0,0](0)
7
[2,1](6) <-- [1,1](1) <-- [0,0](0)
4
[2,2](3) <-- [1,1](1) <-- [0,0](0)
7
[2,3](3) <-- [2,2](3) <-- [1,1](1) <-- [0,0](0)
7
[2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
11
[2,5](4) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
3
[3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
3
[3,1](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
8
[3,2](5) <-- [3,1](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
11
[3,3](7) <-- [2,2](3) <-- [1,1](1) <-- [0,0](0)
10
[3,4](3) <-- [2,3](3) <-- [2,2](3) <-- [1,1](1) <-- [0,0](0)
8
[3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
4
[4,0](1) <-- [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
12
[4,1](9) <-- [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
12
[4,2](9) <-- [3,1](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
16
[4,3](8) <-- [3,2](5) <-- [3,1](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
10
[4,4](2) <-- [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
13
[4,5](5) <-- [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
5
[5,0](1) <-- [4,0](1) <-- [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
13
[5,1](9) <-- [4,0](1) <-- [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
14
[5,2](2) <-- [4,1](9) <-- [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
19
[5,3](9) <-- [4,4](2) <-- [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
12
[5,4](2) <-- [4,4](2) <-- [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
10 [5,5](0) <-- [4,4](2) <-- [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
2013-02-04 13:34
