门户网站的发展趋势,宝塔面板如何安装wordpress,网站前端包括哪些,如何关闭wordpress默认编辑器求有向图中的最短路径(JAVADFS算法实现)问题描述给定一个有向图#xff0c;如下图所示#xff0c;求从1号顶点到5号顶点的最短路径。输入数据格式为第一行输入顶点数和边数#xff0c;从第二行开始每一行输入3个整数#xff0c;分别代表连接顶点的边和权重。例如#xff1…求有向图中的最短路径(JAVADFS算法实现)问题描述给定一个有向图如下图所示求从1号顶点到5号顶点的最短路径。输入数据格式为第一行输入顶点数和边数从第二行开始每一行输入3个整数分别代表连接顶点的边和权重。例如1 2 2表示从1号顶点到2号顶点连接的边权重为2。Input5 81 2 21 5 102 3 32 5 73 1 43 4 44 5 55 3 3Output9算法实现package com.bean.algorithm.graph3;import java.util.Scanner;public class ShortestPath {static int min Integer.MAX_VALUE;static int[][] edge new int[100][100];static int[] vertex new int[100];static int n, m;static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 1; i n; i) {for (int j 1; j m; j) {if (i j) {edge[i][j] 0;} else {edge[i][j] Integer.MAX_VALUE;}}}for (int i 1; i m; i) {int a input.nextInt();int b input.nextInt();int c input.nextInt();edge[a][b] c;}vertex[1] 1;dfs(1, 0);System.out.println(min);}public static void dfs(int cur, int dis) {/*** 如果当前路径大于之前找到的最小值可直接返回* */if (dis min) {return;}/*** 判断是否达到最后一个结点更新最小值返回* */if(cur n) {if (dis min) {min dis;return;}}/*** 当前点到其他各点之间可连通但是还未添加进来时遍历执行* */for (int i 1; i n; i) {if (edge[cur][i] ! Integer.MAX_VALUE vertex[i] 0) {vertex[i] 1;dfs(i, disedge[cur][i]);/*** 回溯**/vertex[i] 0;}}return;}}程序运行结果9
