floyd演算法java

『叄』 Floyd演算法的參考代碼

function Floyd(w,router_direction,MAX)
%w為此圖的距離矩陣
%router_direction為路由類型：0為前向路由；非0為回溯路由
%MAX是數據輸入時的∞的實際值
len=length(w);
flag=zeros(1,len);
%根據路由類型初始化路由表
R=zeros(len,len);
for i=1:len
if router_direction==0%前向路由
R(:,i)=ones(len,1)*i;
else %回溯路由
R(i,:)=ones(len,1)*i;
end
R(i,i)=0;
end
disp('');
disp('w(0)');
dispit(w,0);
disp('R(0)');
dispit(R,1);
%處理端點有權的問題
for i=1:len
tmp=w(i,i)/2;
if tmp~=0
w(i,:)=w(i,:)+tmp;
w(:,i)=w(:,i)+tmp;
flag(i)=1;
w(i,i)=0;
end
end
%Floyd演算法具體實現過程
for i=1:len
for j=1:len
if j==i || w(j,i)==MAX
continue;
end
for k=1:len
if k==i || w(j,i)==MAX
continue;
end
if w(j,i)+w(i,k)<w(j,k) %Floyd演算法核心代碼
w(j,k)=w(j,i)+w(i,k);
if router_direction==0%前向路由
R(j,k)=R(j,i);
else %回溯路由
R(j,k)=R(i,k);
end
end
end
end
%顯示每次的計算結果
disp(['w(',num2str(i),')'])
dispit(w,0);
disp(['R(',num2str(i),')'])
dispit(R,1);
end
%中心和中點的確定
[Center,index]=min(max(w'));
disp(['中心是V',num2str(index)]);
[Middle,index]=min(sum(w'));
disp(['中點是V',num2str(index)]);
end
function dispit(x,flag)
%x：需要顯示的矩陣
%flag：為0時表示顯示w矩陣，非0時表示顯示R矩陣
len=length(x);
s=[];
for j=1:len
if flag==0
s=[s sprintf('%5.2f ',x(j,:))];
else
s=[s sprintf('%d ',x(j,:))];
end
s=[s sprintf(' ')];
end
disp(s);
disp('---------------------------------------------------');
end
% 選擇後按Ctrl+t取消注釋號%
%
% 示例：
% a=[
% 0,100,100,1.2,9.2,100,0.5;
% 100,0,100,5,100,3.1,2;
% 100,100,0,100,100,4,1.5;
% 1.2,5,100,0,6.7,100,100;
% 9.2,100,100,6.7,0,15.6,100;
% 100,3.1,4,100,15.6,0,100;
% 0.5,2,1.5,100,100,100,0
% ];
%
% b=[
% 0,9.2,1.1,3.5,100,100;
% 1.3,0,4.7,100,7.2,100;
% 2.5,100,0,100,1.8,100;
% 100,100,5.3,0,2.4,7.5;
% 100,6.4,2.2,8.9,0,5.1;
% 7.7,100,2.7,100,2.1,0
% ];
%
% Floyd(a,1,100)
% Floyd(b,1,100) program floyd;
var
st,en,f:integer;
k,n,i,j,x:integer;
a:array[1..10,1..10] of integer;
path:array[1..10,1..10] of integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(k);
if k<>0 then
a[i,j]:=k
else
a[i,j]:=maxint;
path[i,j]:=j;
end;
readln;
end;
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,x]+a[x,j] then
begin
a[i,j]:=a[i,x]+a[x,j];
path[i,j]:=path[i,x];
end;
readln(st,en);
writeln(a[st,en]);
f:=st;
while f<> en do
begin
write(f);
write('-->');
f:=path[f,en];
end;
writeln(en);
end. //以無向圖G為入口，得出任意兩點之間的路徑長度length[i][j]，路徑path[i][j][k]，//途中無連接得點距離用0表示，點自身也用0表示publicclassFLOYD{int[][]length=null;//任意兩點之間路徑長度int[][][]path=null;//任意兩點之間的路徑publicFLOYD(int[][]G){intMAX=100;introw=G.length;//圖G的行數int[][]spot=newint[row][row];//定義任意兩點之間經過的點int[]onePath=newint[row];//記錄一條路徑length=newint[row][row];path=newint[row][row][];for(inti=0;i<row;i++)//處理圖兩點之間的路徑for(intj=0;j<row;j++){if(G[i][j]==0)G[i][j]=MAX;//沒有路徑的兩個點之間的路徑為默認最大if(i==j)G[i][j]=0;//本身的路徑長度為0}for(inti=0;i<row;i++)//初始化為任意兩點之間沒有路徑for(intj=0;j<row;j++)spot[i][j]=-1;for(inti=0;i<row;i++)//假設任意兩點之間的沒有路徑onePath[i]=-1;for(intv=0;v<row;++v)for(intw=0;w<row;++w)length[v][w]=G[v][w];for(intu=0;u<row;++u)for(intv=0;v<row;++v)for(intw=0;w<row;++w)if(length[v][w]>length[v][u]+length[u][w]){length[v][w]=length[v][u]+length[u][w];//如果存在更短路徑則取更短路徑spot[v][w]=u;//把經過的點加入}for(inti=0;i<row;i++){//求出所有的路徑int[]point=newint[1];for(intj=0;j<row;j++){point[0]=0;onePath[point[0]++]=i;outputPath(spot,i,j,onePath,point);path[i][j]=newint[point[0]];for(ints=0;s<point[0];s++)path[i][j][s]=onePath[s];}}}voidoutputPath(int[][]spot,inti,intj,int[]onePath,int[]point){//輸出i//到j//的路徑的實際代碼，point[]記錄一條路徑的長度if(i==j)return;if(spot[i][j]==-1)onePath[point[0]++]=j;//System.out.print(+j+);else{outputPath(spot,i,spot[i][j],onePath,point);outputPath(spot,spot[i][j],j,onePath,point);}}publicstaticvoidmain(String[]args){intdata[][]={{0,27,44,17,11,27,42,0,0,0,20,25,21,21,18,27,0},//x1{27,0,31,27,49,0,0,0,0,0,0,0,52,21,41,0,0},//1{44,31,0,19,0,27,32,0,0,0,47,0,0,0,32,0,0},//2{17,27,19,0,14,0,0,0,0,0,30,0,0,0,31,0,0},//3{11,49,0,14,0,13,20,0,0,28,15,0,0,0,15,25,30},//4{27,0,27,0,13,0,9,21,0,26,26,0,0,0,28,29,0},//5{42,0,32,0,20,9,0,13,0,32,0,0,0,0,0,33,0},//6{0,0,0,0,0,21,13,0,19,0,0,0,0,0,0,0,0},//7{0,0,0,0,0,0,0,19,0,11,20,0,0,0,0,33,21},//8{0,0,0,0,28,26,32,0,11,0,10,20,0,0,29,14,13},//9{20,0,47,30,15,26,0,0,20,10,0,18,0,0,14,9,20},//10{25,0,0,0,0,0,0,0,0,20,18,0,23,0,0,14,0},//11{21,52,0,0,0,0,0,0,0,0,0,23,0,27,22,0,0},//12{21,21,0,0,0,0,0,0,0,0,0,0,27,0,0,0,0},//13{18,41,32,31,15,28,0,0,0,29,14,0,22,0,0,11,0},//14{27,0,0,0,25,29,33,0,33,14,9,14,0,0,11,0,9},//15{0,0,0,0,30,0,0,0,21,13,20,0,0,0,0,9,0}//16};for(inti=0;i<data.length;i++)for(intj=i;j<data.length;j++)if(data[i][j]!=data[j][i])return;FLOYDtest=newFLOYD(data);for(inti=0;i<data.length;i++)for(intj=i;j<data[i].length;j++){System.out.println();System.out.print(From+i+to+j+pathis:);for(intk=0;k<test.path[i][j].length;k++)System.out.print(test.path[i][j][k]+);System.out.println();System.out.println(From+i+to+j+length:+test.length[i][j]);}}}

『肆』 誰可以用JAVA語言floyd演算法，幫我解決一下這個題目

這題目其實就是單純的求最長的一條路徑而已,距離函數依然滿足三角不等式,所以不用管它.

而且因為他是一棵樹,甚至都不用floyd,直接樹形遍歷都可以

『伍』 floyd演算法求最短路徑

Floyd演算法適用於APSP(AllPairsShortestPaths)，是一種動態規劃演算法，稠密圖效果最佳，邊權可正可負。此演算法簡單有效，由於三重循環結構緊湊，對於稠密圖，效率要高於執行|V|次Dijkstra演算法。

優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單

缺點：時間復雜度比較高，不適合計算大量數據。

時間復雜度:O(n^3)；空間復雜度:O(n^2)；

任意節點i到j的最短路徑兩種可能：

直接從i到j；
從i經過若干個節點k到j。
map（i，j）表示節點i到j最短路徑的距離，對於每一個節點k，檢查map（i，k）+map（k，j）小於map(i，j),如果成立，map（i，j） = map（i，k）+map（k，j）；遍歷每個k，每次更新的是除第k行和第k列的數。

步驟：

第1步：初始化map矩陣。
矩陣中map[i][j]的距離為頂點i到頂點j的權值；

如果i和j不相鄰，則map[i][j]=∞。

如果i==j，則map[i][j]=0;
第2步：以頂點A(假設是第1個頂點)為中介點，若a[i][j] > a[i][1]+a[1][j]，則設置a[i][j]=a[i][1]+a[1][j]。

『陸』 哈密頓迴路 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();

}

『柒』 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直接相連。

『捌』 floyd演算法能不能保證有最優解

Floyd演算法又稱為弗洛伊德演算法，插點法，是一種用於尋找給定的加權圖中頂點間最短路徑的演算法。

演算法過程:

把圖用鄰接距陣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直接相連。

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

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