求可通路径的计算方法！

Question

http://www.sourceforge.net/projects/jgraph. 
在sourceforge这个网站有很多免费软件，你可以找到JGraphT这个Java写的图论工具，
它实现了图的表示和遍历算法，用它再编写其他图论的算法很方便。

Answer 1

All Textbooks should discuss them

Answer 2

下面是上学期学DS的时候写的Dijkstra算法:
1.图和边的定义
//ADT of Graph
interface Graph{
public int n();
public int e();
public Edge first(int v);
public Edge next(Edge w);
public boolean isEdge(Edge w);
public boolean isEdge(int i,int j);
public int v1(Edge w);
public int v2(Edge w);
public void setEdge(int i,int j,int weight);
public void setEdge(Edge w,int weight);
public void delEdge(Edge w);
public void delEdge(int i,int j);
public int weight(int i,int j);
public int weight(Edge w);
public void setMark(int v,int val);
public int getMark(int v);
}
interface Edge{
public int v1();
public int v2();
}
2.邻接矩阵表示图
//Edge class for aadjacency graph representation
class Edgem implements Edge{
private int vert1,vert2; public Edgem(int v1,int v2){
vert1 = v1;
vert2 = v2;
} public int v1(){return vert1;}
public int v2(){return vert2;}
}
class Graphm implements Graph{
private int[][] matrix;
private int numEdge;
public int[] Mark; public Graphm(int n){
Mark = new int[n];
matrix = new int[n][n];
numEdge = 0;
} public int n(){return Mark.length;}
public int e(){return numEdge;} public Edge first(int v){
for(int i = 0;i < Mark.length;i++)
if(matrix[v][i] != 0)
return new Edgem(v,i);
return null;
} public Edge next(Edge w){
if(w == null) return null;
for(int i = w.v2() + 1;i < Mark.length;i++)
if(matrix[w.v1()][i] != 0)
return new Edgem(w.v1(),i);
return null;
} public boolean isEdge(Edge w){
if(w == null) return false;
else return matrix[w.v1()][w.v2()] != 0;
} public boolean isEdge(int i,int j){
return matrix[i][j] != 0;
} public int v1(Edge w){return w.v1();}
public int v2(Edge w){return w.v2();} public void setEdge(int i,int j,int wt){
Assert.notFalse(wt != 0,"Can not set weight to 0");
matrix[i][j] = wt;
matrix[j][i] = wt;
numEdge++;
}
/*
public void setEdge(int i,int j,int m){
if(m == 1){//whether it is directed graph
matrix[i][j] = 1;
}
else {
matrix[i][j] = 1;
matrix[j][i] = 1;
}
}
*/ public void setEdge(Edge w,int weight){
if(w != null)
setEdge(w.v1(),w.v2(),weight);
}
public void delEdge(Edge w){
if(w != null)
if(matrix[w.v1()][w.v2()] != 0){
matrix[w.v1()][w.v2()] = 0;
numEdge--;
}
}
public void delEdge(int i,int j){
if(matrix[i][j] != 0){
matrix[i][j] = 0;
numEdge--;
}
} public int weight(int i,int j){
if(matrix[i][j] == 0) return Integer.MAX_VALUE;
else return matrix[i][j];
}
public int weight(Edge w){
return weight(w.v1(),w.v2());
} public void setMark(int v,int val){
Mark[v] = val;
}
public int getMark(int v){
return Mark[v];
}
}

Answer 3

3.Dijkstra的Method
public static void DijkstraH(Graph G,int s,int[] D){
  int v;
  DijkElem[] E = new DijkElem[G.e()];
  E[0] = new DijkElem(s,0);
  MinHeap H = new MinHeap(E,1,G.e());
  for(int i = 0;i < G.n();i++)
  D[i] = Integer.MAX_VALUE;
  D[s] = 0;
  for(int i = 0;i < G.n();i++){
  do{v = ((DijkElem)H.removemin()).vertex();}
  while(G.getMark(v) == VISITED);
  G.setMark(v,VISITED);
  if(D[v] == Integer.MAX_VALUE) return;
  for(Edge w = G.first(v);G.isEdge(w);w = G.next(w)){
  if(D[G.v2(w)] > (D[v] + G.weight(w))){
  D[G.v2(w)] = D[v] + G.weight(w);
  H.insert(new DijkElem(G.v2(w),D[G.v2(w)]));
  }
  }
  }
  }
4.Method中用到的最小值堆
public class MinHeap{
private Elem[] Heap;
private int size;
private int n; public MinHeap(Elem[] h,int num,int max){
Heap = h;n = num;size = max;buildheap();
} public int heapSize(){
return n;
} public boolean isLeaf(int pos){
return (pos >= n/2) && (pos < n);
} public int leftchild(int pos){
Assert.notFalse(pos < n/2,"Position has no left child");
return 2 * pos + 1;
} public int rightchild(int pos){
Assert.notFalse(pos < (n - 1)/2,"Position has no right child");
return 2 * pos + 2;
} public int parent(int pos){
Assert.notFalse(pos > 0,"Position has no parent");
return (pos - 1) / 2;
}
public void buildheap(){
for(int i = n/2 - 1;i >= 0;i--) siftdown(i);
}
private void siftdown(int pos){
Assert.notFalse((pos >= 0) && (pos < n),"Illegal heap position");
while(! isLeaf(pos)){
int j = leftchild(pos);
if((j < (n - 1)) && (Heap[j].key() > Heap[j + 1].key()))
j++;
if(Heap[pos].key() <= Heap[j].key()) return;
Dsutil.swap(Heap,pos,j);
pos = j;
}
}
public void insert(Elem val){
Assert.notFalse(n < size,"Heap is full");
int curr = n++;
Heap[curr] = val;
while((curr != 0) && (Heap[curr].key() < Heap[parent(curr)].key())){
Dsutil.swap(Heap,curr,parent(curr));
curr = parent(curr);
}
}
public Elem removemin(){
Assert.notFalse(n > 0,"Removing from empty Heap");
Dsutil.swap(Heap,0,--n);
if(n != 0)
siftdown(0);
return Heap[n];
}
public Elem remove(int pos){
Assert.notFalse((pos > 0) && (pos < n),"Illegal heap position");
Dsutil.swap(Heap,pos,--n);
if(n != 0)
siftdown(pos);
return Heap[n];
}
}

Answer 4

5.  //Floyd算法,求任意两点之间的最短距离
  public static void Floyd(Graph G,int[][] D){
  for(int i = 0;i < G.n();i++)
  for(int j = 0;j < G.n();j++){
    D[i][j] = G.weight(i,j);
D[i][i] = 0;
  }
  for(int i = 0;i < G.n();i++)
  for(int j = 0;j < G.n();j++)
     for(int k = 0;k < G.n();k++)
        if((D[i][k] != Integer.MAX_VALUE) &&
             (D[k][j] != Integer.MAX_VALUE)  &&
             (D[i][j] > (D[i][k] + D[k][j])))
  D[i][j] = D[i][k] + D[k][j];
  }

Answer 5

例如：
A----B----F
    / \  / \
  C    D -- E如上图，求解A到F的所有路径！

Answer 6

你的问题更简单,还不用Dijsktra和Floyd的算法就解决了,照着上面定义的图的表示,用邻接矩阵表示,然后用一些回溯就没问题了^_^

Answer 7

我只能给你提供思路,确实忙,不能把完整程序写出来,见谅:)代码就自己动手吧^_^
先把邻接矩阵写出来
先沿着一条路走,走到一个节点把一个节点置成visited,a->b->c,没有路了,回溯,在走a->b->f,找到f,然后把这条路径加入到一个比如ArrayList中吧,然后把f回复成unvisited,然后沿着下一条路径继续找.....