城市最短距离25-01-15

题目 #

题目描述 #

一天小明捧着一本世界地图在看，突然小明拿起笔，将他最爱的那些城市标记出来，并且随机的将这些城市中的某些用线段两两连接起来。 小明量出了每条线段的长度，现在小明想知道在这些线段组成的图中任意两个城市之间的最短距离是多少。

输入描述 #

输入包含多组测试数据。 每组输入第一行为两个正整数n（n<=10）和m（m<=n*(n-1)/2），n表示城市个数，m表示线段个数。 接下来m行，每行输入三个整数a，b和l，表示a市与b市之间存在一条线段，线段长度为l。（a与b不同） 每组最后一行输入两个整数x和y，表示问题：x市与y市之间的最短距离是多少。（x与y不同） 城市标号为1~n，l<=20。

输出描述 #

对于每组输入，输出x市与y市之间的最短距离，如果x市与y市之间非连通，则输出“No path”。

输入示例 #
4 4
1 2 4
1 3 1
1 4 1
2 3 1
2 4
输出示例 #
3

解答 #

dijkstra解答 #

import java.io.*;
import java.util.*;

public class Main{
    static int[][] edge;
    public static int getMinPath(int origin,int target,int numCity){
        int[] dist=new int[numCity+1];
        int[] path=new int[numCity+1];
        int[] visit=new int[numCity+1];
        int noVisitNum=numCity-1;
        for(int i=0;i<numCity+1;i++){
            if(i==origin)continue;
            if(edge[origin][i]!=0){
                dist[i]=edge[origin][i];
                path[i]=origin;
            }else{
                dist[i]=Integer.MAX_VALUE;
                path[i]=-1;
            }
        }
        
        for(int i=1;i<numCity+1;i++){
            if(i==origin)visit[i]=1;
            visit[i]=0;
        }
        while(noVisitNum>0){
            int minDist=Integer.MAX_VALUE;
            int tempIndex=-1;
            for(int i=1;i<numCity+1;i++){
                if(i==origin)continue;
                if(visit[i]==0){
                    if(dist[i]<minDist){
                        tempIndex=i;
                        minDist=dist[i];
                    }
                }
            }
            
            if(tempIndex==-1)break;
            visit[tempIndex]=1;
            for(int i=1;i<numCity+1;i++){
                if(i==tempIndex)continue;
                if(edge[tempIndex][i]!=0 &&visit[i]==0 ){
                    if(dist[tempIndex]+edge[tempIndex][i]<dist[i]){
                        dist[i]=dist[tempIndex]+edge[tempIndex][i];
                        path[i]=tempIndex;
                    }
                }
            }
            noVisitNum--;
            visit[tempIndex]=1;
        }
        return dist[target];
        
    }
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line;
        while((line=in.readLine())!=null){
            String[] tempArr=line.split(" ");
            int n=Integer.parseInt(tempArr[0]);
            int m=Integer.parseInt(tempArr[1]);
            edge=new int[n+1][n+1];
            int temp_m=m;
            while(temp_m>0){
                line=in.readLine();
                tempArr=line.split(" ");
                int a=Integer.parseInt(tempArr[0]); 
                int b=Integer.parseInt(tempArr[1]);
                int dist=Integer.parseInt(tempArr[2]);
                edge[a][b]=dist;
                edge[b][a]=dist;
                temp_m--;
            }
            line=in.readLine();
            tempArr=line.split(" ");
            int x=Integer.parseInt(tempArr[0]); 
            int y=Integer.parseInt(tempArr[1]);
            int dist=getMinPath(x,y,n);
            if(dist==Integer.MAX_VALUE){
                out.println("No path");
            }else{
                out.println(dist);
            }
            
        }
        out.flush();
    }
}

属于无向图的求解

时间复杂度： O(N2) O(N^2) N为节点个数

在迪杰斯特拉算法的求解中，重要的一个问题是如何确定 不可达的值设定，如果设定为 -1，在进行值的比较的时候，有一点不方便，直接使用 ∞ \infin 方便一点

Floyd算法 #

import java.io.*;
import java.util.*;
 
public class Main{
    static int[][] edge;
    public static int getMinPath(int origin,int target,int numCity,PrintWriter out){
        int[][] dist=new int[numCity+1][numCity+1];
        int[][] path=new int[numCity+1][numCity+1];
        for(int i=1;i<numCity+1;i++){
            for(int j=1;j<numCity+1;j++){
                if(edge[i][j]==0&&i!=j){
                    dist[i][j]=Integer.MAX_VALUE;
                    edge[i][j]=Integer.MAX_VALUE;
                    path[i][j]=-1;
                }else{
                    dist[i][j]=edge[i][j];
                    path[i][j]=i;
                }
                
            }
        }
        //out.print(Arrays.deepToString(dist));
        for(int i=1;i<numCity+1;i++){
            //考虑新的点
            for(int j=1;j<numCity+1;j++){
                for(int k=1;k<numCity+1;k++){
                    if(dist[j][i]!=Integer.MAX_VALUE && dist[i][k]!=Integer.MAX_VALUE){
                        int newDis=dist[j][i]+dist[i][k];
                    if(newDis<dist[j][k]){
                        dist[j][k]=newDis;
                        path[j][k]=i;
                    }
                    }
                    
                }
            }
        }
        //out.print(Arrays.deepToString(dist));
        return dist[origin][target];
    }
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line;
        while((line=in.readLine())!=null){
            String[] tempArr=line.split(" ");
            int n=Integer.parseInt(tempArr[0]);
            int m=Integer.parseInt(tempArr[1]);
            edge=new int[n+1][n+1];
            int temp_m=m;
            while(temp_m>0){
                line=in.readLine();
                tempArr=line.split(" ");
                int a=Integer.parseInt(tempArr[0]); 
                int b=Integer.parseInt(tempArr[1]);
                int dist=Integer.parseInt(tempArr[2]);
                edge[a][b]=dist;
                edge[b][a]=dist;
                temp_m--;
            }
            line=in.readLine();
            tempArr=line.split(" ");
            int x=Integer.parseInt(tempArr[0]); 
            int y=Integer.parseInt(tempArr[1]);
            int dist=getMinPath(x,y,n,out);
            if(dist==Integer.MAX_VALUE){
                out.println("No path");
            }else{
                out.println(dist);
            }
             
        }
        out.flush();
    }
}

关键信息：在使用dist矩阵进行一步步迭代的过程中，edge矩阵不再被使用，因为其信息已经过时，使用的衡量距离的矩阵一直是dist而不是edge（边的原始关系矩阵）

时间复杂度： O(N3)O(N^3)

深度优先搜索 #

import java.io.*;
import java.util.*;
 
public class Main{
    static int[][] edge;
    static int min=Integer.MAX_VALUE;
    static int citys;
    public static void dfs(int target,int distance,int current,int[] visit){
        if(distance>=min) return;
        
        for(int i=1;i<citys+1;i++ ){
            
            if(edge[current][i]==Integer.MAX_VALUE) continue;
            if(visit[i]==1) continue;
            if(i==current)continue;
            if(i==target){
                int newD=distance+edge[current][i];
                if(newD<min){
                    min=newD;
                }
                return;
            }
            visit[i]=1;
            dfs(target,distance+edge[current][i],i,visit);
            visit[i]=0;
            
        }
    }
    public static void getMinPath(int origin,int target,int numCity,PrintWriter out){
        
        for(int i=1;i<numCity+1;i++){
            for(int j=1;j<numCity+1;j++){
                if(edge[i][j]==0&&i!=j){
                    
                    edge[i][j]=Integer.MAX_VALUE;
                    
                }
                
            }
        }
        int[] isVisit=new int[numCity+1];
        dfs(target,0,origin,isVisit);
        
    }
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line;
        while((line=in.readLine())!=null){
            String[] tempArr=line.split(" ");
            int n=Integer.parseInt(tempArr[0]);
            int m=Integer.parseInt(tempArr[1]);
            edge=new int[n+1][n+1];
            min=Integer.MAX_VALUE;
            int temp_m=m;
            citys=n;
            while(temp_m>0){
                line=in.readLine();
                tempArr=line.split(" ");
                int a=Integer.parseInt(tempArr[0]); 
                int b=Integer.parseInt(tempArr[1]);
                int dist=Integer.parseInt(tempArr[2]);
                edge[a][b]=dist;
                edge[b][a]=dist;
                temp_m--;
            }
            line=in.readLine();
            tempArr=line.split(" ");
            int x=Integer.parseInt(tempArr[0]); 
            int y=Integer.parseInt(tempArr[1]);
            getMinPath(x,y,n,out);
            if(min==Integer.MAX_VALUE){
                out.println("No path");
            }else{
                out.println(min);
            }
             
        }
        out.flush();
    }
}

注意点：

  • 使用visit数组保存即将dfs的结果
  • 在dfs结束之后及时还原结果，保证visit可以重复使用
  • 一维数组即可保存全部访问的结果

在函数中，要放对位置

visit[i]=1;
dfs(target,distance+edge[current][i],i,visit);
visit[i]=0;

如果在函数开头就进行visit[current]==1 return的判断的话，在后期不方便进行还原

时间复杂度：

dp[i][j]=max⁡{dp[i−1][j−1]+1,dp[i−1][j],dp[i][j−1]. \text{dp}[i][j] = \max\left\{\begin{aligned}&\text{dp}[i-1][j-1] + 1, \\&\text{dp}[i-1][j], \\&\text{dp}[i][j-1].\end{aligned}\right. \[ \text{dp}[i][j] = \max\left\{\begin{aligned}&\text{dp}[i-1][j-1] + 1, \\&\text{dp}[i-1][j], \\&\text{dp}[i][j-1].\end{aligned}\right. \] \[ f(x) = \int_{-\infty}^\infty\hat f(\xi),e^{2 \pi i \xi x},d\xi \]

完 \(\pi(x)\) ,全图： O(N!)O(N!) 稀疏图： O(MN)O(M N)

顶部 首页 上一篇 下一篇