# 迪杰斯特拉（Dijstra）算法和弗洛伊德（Floyd）算法

**Published by:** [nnnnnobita](https://paragraph.com/@nnnnnobita/)
**Published on:** 2021-12-04
**URL:** https://paragraph.com/@nnnnnobita/dijstra-floyd

## Content

迪杰斯特拉 找到某一个顶点到其他所有顶点的最短距离 弗洛伊德 找到所有顶点之间的最短距离package Algorithm.floyd; import java.util.Arrays; public class floydDemo { public static void main(String[] args) { final int N = 65535; char[] vertex = {'A','B','C','D','E','F','G'}; int[][] weight = new int[][] { {0,5,7,N,N,N,2}, {5,0,N,9,N,N,3}, {7,N,0,N,8,N,N}, {N,9,N,0,N,4,N}, {N,N,8,N,0,5,4}, {N,N,N,4,5,0,6}, {2,3,N,N,4,6,0}, }; Graph graph = new Graph(vertex.length, weight, vertex); graph.floyd(); graph.showAll(); } } class Graph{ private char[] vertex; private int[][] dis; private int[][] pre; public Graph(int length, int[][] dis, char[] vertex) { this.vertex = vertex; this.dis = dis; this.pre = new int[length][length]; for(int i=0; i<vertex.length; i++) { Arrays.fill(pre[i], i); //pre[i]是第i行 } } public void showAll() { for(int i=0; i<vertex.length; i++) { //输出pre for(int j=0; j<vertex.length; j++) { System.out.print(pre[i][j] + " "); } System.out.println(); //输出dis for(int j=0; j<vertex.length; j++) { System.out.print(dis[i][j] + " "); } System.out.println(); } } public void floyd() { int len; // 临时变量记录经过中间节点的新的距离 for(int k=0; k<vertex.length; k++) { // k表示中间节点 for(int i=0; i<vertex.length; i++) { // i表示出发节点 for(int j=0; j<vertex.length; j++) { len = dis[i][k] + dis[k][j]; if(len < dis[i][j]) { //如果len小于两点之间的直接距离，就可以替换了 dis[i][j] = len; // update the distance between i and j pre[i][j] = pre[k][j]; // update the pre-vertex of i,j } } } } } }

## Publication Information

- [nnnnnobita](https://paragraph.com/@nnnnnobita/): Publication homepage
- [All Posts](https://paragraph.com/@nnnnnobita/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@nnnnnobita): Subscribe to updates