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();

}