javafloyd演算法

C. Floyd演算法的優缺點分析

Floyd演算法適用於APSP(All Pairs Shortest Paths，多源最短路徑)，是一種動態規劃演算法，稠密圖效果最佳，邊權可正可負。此演算法簡單有效，由於三重循環結構緊湊，對於稠密圖，效率要高於執行|V|次Dijkstra演算法，也要高於執行V次SPFA演算法。
優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單。
缺點：時間復雜度比較高，不適合計算大量數據。

D. Floyd演算法的演算法過程

1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，如果兩點之間沒有邊相連，則權為無窮大。
2，對於每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。
把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=無窮大。定義一個矩陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經過的點，初始化D[i,j]=j。把各個頂點插入圖中，比較插點後的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。
比如，要尋找從V5到V1的路徑。根據D，假如D(5,1)=3則說明從V5到V1經過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。

E. 最短路徑的floyd演算法的時間復雜度

Floyd：每對節點之間的最短路徑。Floyd-Warshall演算法（Floyd-Warshall
algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用於計算有向圖的傳遞閉包。Floyd-Warshall演算法的時間復雜度為O(N3)，空間復雜度為O(N2)。

先給出結論：

(1)當權值為非負時，用Dijkstra。

(2)當權值有負值，且沒有負圈，則用SPFA，SPFA能檢測負圈，但是不能輸出負圈。

(3)當權值有負值，而且可能存在負圈，則用BellmanFord，能夠檢測並輸出負圈。

(4)SPFA檢測負環：當存在一個點入隊大於等於V次，則有負環，後面有證明。

F. 求數據結構公交線路咨詢的代碼用java，其中求最短路徑用Floyd演算法

不知道你想怎麼搞 反正感覺A*演算法也可以，網上一大堆，還有就是Dijkstra演算法

G. 哈密頓迴路 JAVA程序

最短路徑問題分兩類，一類是單源最短路徑問題，就是從指定頂點出發到其他各點的最短距離，還有一類是
每兩個遲毀皮頂點之間的最短距離，當然第二類也可以通過對每個頂點做一次單源最短路徑求解，但是還有一種更優雅的方法（Floyd演算法），這種方法一般使用相鄰矩陣的實現方式，對每個頂點看它是不是能作為其它沒兩對頂點間的碼差直接中間節點，如果能，那麼再看是不是通過它的兩兩頂點的距離是不是減小了，若果是就更新這兩對頂點間的距離，這樣通過每次「余好貪婪的」找出局部最優解來得到全局最優解，可以算是一個動態規劃的解法。
首先我們需要一個輔助類來保存距離，以及回溯路徑的類：
public static class Dist implements Comparable<Dist>
{
public int preV;
public int curV;
public int distance;

public Dist(int v)
{
this.curV=v;
this.preV=-1;
this.distance=Integer.MAX_VALUE;
}

@Override
public int compareTo(Dist other) {
return distance-other.distance;
}

}
下面給出第二類最短路徑的解法（Floyd演算法）Java實現：
@Override
public void floyd(Dist[][] dists) {
for(int i=0;i<numVertexes;i++)
{
dists[i]=new Dist[numVertexes];
for(int j=0;j<numVertexes;j++)
{
dists[i][j]=new Dist(-1);//
dists[i][j].preV=-1;
if(i==j)
dists[i][j].distance=0;

else
dists[i][j].distance=Integer.MAX_VALUE;

}
}

for(int v=0;v<numVertexes;v++)
{
for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e))
{
int to=toVertex(e);
dists[v][to].distance=e.getWeight();
dists[v][to].preV=v;
}
}

for(int v=0;v<numVertexes;v++)
{
for(int i=0;i<numVertexes;i++)
for(int j=0;j<numVertexes;j++)
{

if((dists[i][v].distance!=Integer.MAX_VALUE)&&(dists[v][j].distance!=Integer.MAX_VALUE)&&(dists[i][v].distance+dists[v][j].distance<dists[i][j].distance))
{
dists[i][j].distance=dists[i][v].distance+dists[v][j].distance;
dists[i][j].preV=v;
}
}
}

}

/**
* A Graph example
* we mark the vertexes with 0,1,2,.14 from left to right , up to down
* S-8-B-4-A-2-C-7-D
* | | | | |
* 3 3 1 2 5
* | | | | |
* E-2-F-6-G-7-H-2-I
* | | | | |
* 6 1 1 1 2
* | | | | |
* J-5-K-1-L-3-M-3-T
*
*/
public static void testFloyd() {
DefaultGraph g=new DefaultGraph(15);
g.setEdge(0, 1, 8);
g.setEdge(1, 0, 8);//its a undirected graph
g.setEdge(1, 2, 4);
g.setEdge(2, 1, 4);
g.setEdge(2, 3, 2);
g.setEdge(3, 2, 2);
g.setEdge(3, 4, 7);
g.setEdge(4, 3, 7);

g.setEdge(0, 5, 3);
g.setEdge(5, 0, 3);
g.setEdge(1, 6, 3);
g.setEdge(6, 1, 3);
g.setEdge(2, 7, 1);
g.setEdge(7, 2, 1);
g.setEdge(3, 8, 2);
g.setEdge(8, 3, 2);
g.setEdge(4, 9, 5);
g.setEdge(9, 4, 5);

g.setEdge(5, 6, 2);
g.setEdge(6, 5, 2);
g.setEdge(6, 7, 6);
g.setEdge(7, 6, 6);
g.setEdge(7, 8, 7);
g.setEdge(8, 7, 7);
g.setEdge(8, 9, 2);
g.setEdge(9, 8, 2);

g.setEdge(10, 5, 6);
g.setEdge(5, 10, 6);
g.setEdge(11, 6, 1);
g.setEdge(6, 11, 1);
g.setEdge(12, 7, 1);
g.setEdge(7, 12, 1);
g.setEdge(13, 8, 1);
g.setEdge(8, 13, 1);
g.setEdge(14, 9, 2);
g.setEdge(9, 14, 2);

g.setEdge(10, 11, 5);
g.setEdge(11, 10, 5);
g.setEdge(11, 12, 1);
g.setEdge(12, 11, 1);
g.setEdge(12, 13, 3);
g.setEdge(13, 12, 3);
g.setEdge(13, 14, 3);
g.setEdge(14, 13, 3);

g.assignLabels(new String[]{"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"});

Dist[][] dists=new Dist[15][15];
g.floyd(dists);

System.out.println("Shortes path from S-T ("+dists[0][14].distance+")is:");
Stack<String> stack=new Stack<String>();
int i=0;
int j=14;
while(j!=i)
{

stack.push(g.getVertexLabel(j));
j=dists[i][j].preV;

}
stack.push(g.getVertexLabel(i));
while(!stack.isEmpty())
{
System.out.print(stack.pop());
if(!stack.isEmpty())System.out.print("->");
}
System.out.println();

}

單源最短路徑問題的解法有Dijstra提出，所以也叫Dijstra演算法。
它把頂點分為兩個集合一個是已求出最短距離的頂點集合V1，另一類是暫未求出的頂點集合V2，而可以證明下一個將求出來（V2中到出發點最短距離值最小）的頂點的最短路徑上的頂點除了該頂點不在V1中外其餘頂點都在V1中。

如此，先把出發點放入V1中（出發點的最短距離當然也就是0），然後每次選擇V2中到出發點距離最短的點加入V1，並把標記改點的最短距離.直到V2中沒有頂點為止，詳細的形式化證明見：
Dijstra演算法證明

這里的實現我們使用最小值堆來每次從V2中挑出最短距離。

先給出最小值堆的實現：
package algorithms;

import java.lang.reflect.Array;

public class MinHeap<E extends Comparable<E>>
{

private E[] values;
int len;

public MinHeap(Class<E> clazz,int num)
{

this.values=(E[])Array.newInstance(clazz,num);
len=0;
}

public final E removeMin()
{
E ret=values[0];
values[0]=values[--len];
shift_down(0);
return ret;
}

//insert to tail
public final void insert(E val)
{
values[len++]=val;
shift_up(len-1);

}

public final void rebuild()
{
int pos=(len-1)/2;
for(int i=pos;i>=0;i--)
{
shift_down(i);
}
}

public final boolean isEmpty()
{
return len==0;
}

/**
* When insert element we need shiftUp
* @param array
* @param pos
*/
private final void shift_up(int pos)
{

E tmp=values[pos];
int index=(pos-1)/2;
while(index>=0)
{
if(tmp.compareTo(values[index])<0)
{
values[pos]=values[index];
pos=index;
if(pos==0)break;
index=(pos-1)/2;
}
else break;
}
values[pos]=tmp;
}
private final void shift_down(int pos)
{

E tmp=values[pos];
int index=pos*2+1;//use left child
while(index<len)//until no child
{
if(index+1<len&&values[index+1].compareTo(values[index])<0)//right child is smaller
{
index+=1;//switch to right child
}
if(tmp.compareTo(values[index])>0)
{
values[pos]=values[index];
pos=index;
index=pos*2+1;

}
else
{
break;
}

}
values[pos]=tmp;

}
}
下面是基於最小值堆的最短路勁演算法以及一個測試方法：

public void dijstra(int fromV,Dist[] dists)
{
MinHeap<Dist> heap=new MinHeap<Dist>(Dist.class,numVertexes*2);

for(int v=0;v<numVertexes;v++)
{
dists[v]=new Dist(v);
}

Arrays.fill(visitTags, false);
dists[fromV].distance=0;
dists[fromV].preV=-1;
heap.insert(dists[fromV]);
int num=0;

while(num<numVertexes)
{
Dist dist=heap.removeMin();
if(visitTags[dist.curV])
{
continue;
}
visitTags[dist.curV]=true;
num++;
for(Edge e=firstEdge(dist.curV);isEdge(e);e=nextEdge(e))
{
if(!visitTags[toVertex(e)]&&e.getWeight()+dist.distance<dists[toVertex(e)].distance)
{

dists[toVertex(e)].distance=e.getWeight()+dist.distance;
dists[toVertex(e)].preV=dist.curV;
heap.insert(dists[toVertex(e)]);

}
}

}

}

/**
* A Graph example
* we mark the vertexes with 0,1,2,.14 from left to right , up to down
* S-8-B-4-A-2-C-7-D
* | | | | |
* 3 3 1 2 5
* | | | | |
* E-2-F-6-G-7-H-2-I
* | | | | |
* 6 1 1 1 2
* | | | | |
* J-5-K-1-L-3-M-3-T
*
*/
public static void testDijstra()
{
DefaultGraph g=new DefaultGraph(15);
g.setEdge(0, 1, 8);
g.setEdge(1, 0, 8);//its a undirected graph
g.setEdge(1, 2, 4);
g.setEdge(2, 1, 4);
g.setEdge(2, 3, 2);
g.setEdge(3, 2, 2);
g.setEdge(3, 4, 7);
g.setEdge(4, 3, 7);

g.setEdge(0, 5, 3);
g.setEdge(5, 0, 3);
g.setEdge(1, 6, 3);
g.setEdge(6, 1, 3);
g.setEdge(2, 7, 1);
g.setEdge(7, 2, 1);
g.setEdge(3, 8, 2);
g.setEdge(8, 3, 2);
g.setEdge(4, 9, 5);
g.setEdge(9, 4, 5);

g.setEdge(5, 6, 2);
g.setEdge(6, 5, 2);
g.setEdge(6, 7, 6);
g.setEdge(7, 6, 6);
g.setEdge(7, 8, 7);
g.setEdge(8, 7, 7);
g.setEdge(8, 9, 2);
g.setEdge(9, 8, 2);

g.setEdge(10, 5, 6);
g.setEdge(5, 10, 6);
g.setEdge(11, 6, 1);
g.setEdge(6, 11, 1);
g.setEdge(12, 7, 1);
g.setEdge(7, 12, 1);
g.setEdge(13, 8, 1);
g.setEdge(8, 13, 1);
g.setEdge(14, 9, 2);
g.setEdge(9, 14, 2);

g.setEdge(10, 11, 5);
g.setEdge(11, 10, 5);
g.setEdge(11, 12, 1);
g.setEdge(12, 11, 1);
g.setEdge(12, 13, 3);
g.setEdge(13, 12, 3);
g.setEdge(13, 14, 3);
g.setEdge(14, 13, 3);

g.assignLabels(new String[]{"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"});

Dist[] dists=new Dist[15];
g.dijstra(0, dists);

System.out.println("Shortes path from S-T ("+dists[14].distance+")is:");
Stack<String> stack=new Stack<String>();
for(int v=dists[14].curV;v!=-1;v=dists[v].preV)
{
stack.push(g.getVertexLabel(v));

}
while(!stack.isEmpty())
{
System.out.print(stack.pop());
if(!stack.isEmpty())System.out.print("->");
}
System.out.println();

}