广州百度网站建设公司,东莞天助网的网站,松江做公司网站,品牌网站建设有什么作用无权图的最短路径思路#xff1a;无权图的最短路径也就是要求两点之间最少几跳可达#xff0c;那么我们可以这样#xff0c;用广度遍历#xff0c;从起点开始一层层遍历#xff0c;如果第一次遍历到终点#xff0c;那么肯定是最短路径。public static void findPath(int …无权图的最短路径思路无权图的最短路径也就是要求两点之间最少几跳可达那么我们可以这样用广度遍历从起点开始一层层遍历如果第一次遍历到终点那么肯定是最短路径。public static void findPath(int start,int end){//创建一个队列来存储LinkedList VNode queuenew LinkedList();queue.offer(nodes[start]);while(!queue.isEmpty()){VNode vnodequeue.peek();isVisit[vnode.index]true;BNode bnodevnode.bnode;//如果结束点已经访问 跳出循环if(isVisit[end])break;//如果他的邻节点都访问或者没有邻节点 跳出循环while(bnode!null){//如果邻节点还没被访问访记录他的上一节点否则不进行记录。这样的话即使到了下一跳有这个顶点记录的也是更的短路径比如说起点A 邻节点有BCD B的邻节点是C此时遍历A的邻节点C的时候就记录C的上一节点是A下次遍历B的领节点因为C已经被访问所以C记录的上一节点还是A这样就保证了最短路径。if(!isVisit[bnode.index]){//用于记录路径nodes[bnode.index].beforevnode;queue.offer(nodes[bnode.index]);isVisit[bnode.index]true;}bnodebnode.next;}queue.pop();}}public static void printPath(int end){VNode nodenodes[end];int count0;String path;while(node!null){pathnode.indexpath;nodenode.before;count;}System.out.println(path长度为:(count-1));}Dijkstra求有权图最短路径Dijkstra思路依次找到最短路径比如起点A先找到距离A路径最短的点比如BAB路径长为1这时候接着往下找比大于等于1的最短路径。通俗讲就是小明很贪心每一次都找挑最短路径。import java.util.Scanner;public class Dijkstra {public static void main(String[] args) {final int MAXInteger.MAX_VALUE;Scanner innew Scanner(System.in);int vNumin.nextInt();int edgeNumin.nextInt();//二维数值用来表示图int graphic[][]new int [vNum][vNum];//flag[v][w]标识 从v0到v点 w是不是在路径上用于记录路径boolean [][] pathnew boolean [vNum][vNum];//标识是否访问过boolean [] isVisitnew boolean[vNum];//v0到各点的最短路径int distance[]new int [vNum];//进行初始化任意两个点的距离无限大for (int i 0; i for (int j 0; j vNum; j) {graphic[i][j]MAX;}}//读取数据设置权值for (int i 0; i edgeNum; i) {graphic[in.nextInt()][in.nextInt()]in.nextInt();}//起点int v0in.nextInt();//结束点int endin.nextInt();in.close();//进行初始化isVisit[v0]true;for (int i 0; i distance.length; i) {distance[i]graphic[0][i];if(graphic[v0][i]{path[i][i]true;path[i][v0]true;}}int v-1;//要找到vNum-1个顶点循环次数为vNum-1for (int i 1; i vNum; i) {int minInteger.MAX_VALUE;//遍历找到目前v0到其他点的最短距离的点,依次找到离起点最近的点for (int j 0; j vNum; j) {if(!isVisit[j]distance[j]{mindistance[j];vj;}}isVisit[v]true;//新的点v加入重新更新从v0到其他点的最短距离for (int k 0; k distance.length; k) {if(!isVisit[k]graphic[v][k]mingraphic[v][k]){distance[k]mingraphic[v][k];//当前的路径是从v到w所以到v0到v的最短路径上的点也是v0到w上的点System.arraycopy(path[v], 0, path[k], 0, path[v].length);path[k][k]true;}}}System.out.print(路径为);for (int i 0; i vNum; i) {if(path[end][i])System.out.print(i );}System.out.println(路径长为distance[end]);}}测试数据6 80 4 300 2 100 5 1001 2 52 3 504 5 604 3 203 5 100 3输出路径为0 3 4 路径长为50Floyd算法求有权图最小路径Floyd思路floyd算法用的dp的思想核心代码for (int k 0; k vNum; k) {if(distance[i][j]distance[i][k]distance[k][j]){distance[i][j]distance[i][k]distance[k][j];indexk;}}求i到j的最短路径通过遍历每一种情况从i跳到k再有k跳到j遍历每一个可能的k值最后求得到最小路径。import java.util.Scanner;public class Floyd {public static void main(String[] args) {final int MAX10000;Scanner innew Scanner(System.in);int vNumin.nextInt();int edgeNumin.nextInt();//二维数值用来表示图int distance[][]new int[vNum][vNum];int [][] pathnew int [vNum][vNum];//进行初始化任意两个点的距离无限大for (int i 0; i for (int j 0; j vNum; j) {distance[i][j]MAX;if(ij)distance[i][j]0;}}//读取数据设置权值for (int i 0; i edgeNum; i) {distance[in.nextInt()][in.nextInt()]in.nextInt();}//起点int v0in.nextInt();//结束点int endin.nextInt();in.close();for (int i 0; i vNum; i) {for (int j 0; j int indexi;for (int k 0; k vNum; k) {if(distance[i][j]distance[i][k]distance[k][j]){distance[i][j]distance[i][k]distance[k][j];indexk;}}path[i][j]index;}}System.out.println(最短路径长为:distance[v0][end]);System.out.print(路径为:end );while(true){if(endv0)break;System.out.print(path[v0][end] );endpath[v0][end];}}}测试数据6 80 4 300 2 100 5 1001 2 52 3 504 5 604 3 203 5 100 3输出最短路径长为:50路径为:3 4 0我觉得分享是一种精神分享是我的乐趣所在不是说我觉得我讲得一定是对的我讲得可能很多是不对的但是我希望我讲的东西是我人生的体验和思考是给很多人反思也许给你一秒钟、半秒钟哪怕说一句话有点道理引发自己内心的感触这就是我最大的价值(这是我喜欢的一句话也是我写博客的初衷)
