Dijkstra、Floyd 求解路径问题

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。 小蓝的图由 2021 个结点组成，依次编号 1 至
2021。 对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点之间没有边相连；如果 a 和 b
的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。 例如：结点 1 和结点 23
之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。 提示：建议使用计算机编程解决问题。

package lanqiaoCup;

public class 路径问题 {
        public static void main(String[] args) {
            int map[][] = new int[2050][2050];
            //构建二维数组
            for(int i=1;i<=2021;i++) {
                for(int j=i;j<=i+21&&j<=2021;j++) {
                    map[i][j] = lcm(j,i);
                }
            }
            //用来表示该点是否已经是最短
            boolean bj[] = new boolean[2050];
            //用来表示 1到其他点的初始路径
            int dis[] = new int[2050];

            
            for(int i=1;i<=2021;i++)
                dis[i]=map[1][i];

            int min,minIdx=0;

            while(!bj[2021]) {
                min = Integer.MAX_VALUE;
                for(int i=2;i<=2021;i++) {
                    if(!bj[i] && dis[i]!=0 && dis[i]<min) {
                        min = dis[i];
                        minIdx = i;
                    }
                }
                bj[minIdx]=true;
                for(int i=minIdx+1;i<=minIdx+21;i++) {
                    if(map[minIdx][i]!=0) {
                        
                        if(dis[i]==0)
                            dis[i] = dis[minIdx]+map[minIdx][i];
                        else{
                            if(dis[minIdx]+map[minIdx][i]<dis[i])
                                dis[i]=dis[minIdx]+map[minIdx][i];
                        }
                    }
                }
            }

            System.out.println(dis[2021]);

        }
        //求最大公约数
        public static int gcd(int x,int y) {
            return x%y!=0 ? gcd(y, x % y) : y;
        }

        //求最小公倍数
        public static int lcm(int x,int y) {
            return x * y / gcd(x, y);
        }
}

public class Floyd {
	static int[][] graph = new int[2050][2050];
	static final int INF = 0x3f3f3f3f;
	
	private static void floyd() {
		for (int k = 1; k <= 2021; k++) {
			for (int i = 1; i <= 2021; i++) {
				for (int j = 1; j <= 2021; j++) {
					if (i != j && graph[i][j] > graph[i][k] + graph[k][j]) {
						graph[i][j] = graph[i][k] + graph[k][j];
					}
				}
			}
		}
	}
	
	private static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	
	public static void main(String[] args) {
		for (int i = 1; i <= 2021; i++) {
			for (int j = 1; j <= 2021; j++) {
				graph[i][j] = INF;
			}
		}
		for (int i = 1; i <= 2021; i++) {
			for (int j = i; j <= i+21; j++) {
				int div = gcd(j, i);
				int lcm = i * j / div;
				graph[i][j] = lcm;
				graph[j][i] = lcm;
			}
		}
		
		floyd();
		
		System.out.println(graph[1][2021]); // 10266837
	}
	
}

最后

以上就是开心溪流为你收集整理的Dijkstra、Floyd 求解路径问题的全部内容，希望文章能够帮你解决Dijkstra、Floyd 求解路径问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。