Floyd算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Floyd算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1419字,纯文字阅读大概需要3分钟。
内容图文
![Floyd算法](/upload/InfoBanner/zyjiaocheng/633/190a3cd02be24d27a8a858ea9bace02b.jpg)
Floyd算法
弗洛伊德算法,用来计算多源最短路径(任意两个点之间的最短路径)
符号描述
- D(i,j)
- 节点i到节点j的最短距离
- N(i,j)
- 节点i到节点j的下一跳节点
思维
- 如果某个节点位于起点到终点的最短路径上
- D(i,j)=D(i,k)+D(k,j)
- 如果某个节点不位于起点到终点的最短路径上
- D(i,j)<D(i,k)+D(k,j)
Java
public class Floyd {
private int [][]graph;
private int size;
private int[][] d;
private int[][] n;
public Floyd(int[][] graph) {
this.graph = graph;
size=graph.length;
d=new int[size][size];
n=new int[size][size];
for (int i=0;i<size;i++)
for (int j=0;j<size;j++){
//拷贝graph
d[i][j]=graph[i][j];
n[i][j]=j;
}
cal();
}
private void cal() {
//经过点
for (int through = 0; through < size; through++){
//d的遍历
for (int start = 0; start < size; start++) {
//通过点和起点重合
if (start == through)
continue;
for (int end = 0; end < size; end++) {
//起点和终点重合或通过点和终点重合
if ( start == end || end == through)
continue;
int distance = d[start][through] + d[through][end];
if (distance < d[start][end]) {
d[start][end] = distance;
n[start][end] = through;
}
}
}
}
}
public void display(int start,int end){
String result=""+start;
while (n[start][end]!=end){
result+="->"+n[start][end];
start=n[start][end];
}
result+="->"+end;
System.out.println(result);
}
public static void main(String[] args) {
int INF=Integer.MAX_VALUE/2;
int[][] graph=new int[][]{
{INF,-1,3,INF,INF},
{INF,INF,3,2,2},
{INF,INF,INF,INF,INF},
{INF,1,5,INF,INF},
{INF,INF,INF,INF,-3}
};
Floyd floyd=new Floyd(graph);
floyd.display(0,4);
}
}
内容总结
以上是互联网集市为您收集整理的Floyd算法全部内容,希望文章能够帮你解决Floyd算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。