题解 | #单源最短路#

/**
 * 用了三种写法来尝试
 */
/**
 * 写法一：完全自己写的，参考教材上的Floyd-Warshall算法
 */
function findShortestPath( n ,  m ,  graph ) {

    let min = Infinity;
    let dist=[];
    for(let i=0;i<n;i++){
        dist[i]=[];
        for(let j=0;j<n;j++){
            if(i==j){
                dist[i][j]=0;
            }
            else{
                dist[i][j]=Infinity;
            }
        }
    }
    graph.forEach(item => {

        dist[item[0]-1][item[1]-1]=Math.min(item[2],dist[item[0]-1][item[1]-1]);
        
    });
    //Floyd-Warshall算法这里有三层循环，能求所有顶点的最短路径，本题只求1-n最短路径，尝试减去一层，测试可通过。
    for(let i=0;i<n;i++){
        for(let k=1;k<n-1;k++){
            let preDist=dist[0][k]+dist[k][i];
            dist[0][i]=Math.min(dist[0][i], preDist);
        }
    }
    return dist[0][n-1];
    
}

/**
 * 写法二：参考别人解题，一个dfs的写法，开始测试是超时的，偶后来把遍历体的i起始值改为用当前值，可通过，但是感觉这样可能会不太严谨，测试用例里没遍历到边可能正好不是最小值，所以能通过
 */
function findShortestPath( n ,  m ,  graph ) {

    let min = Infinity;
    const dfs = (cur, l, dst, arr, used)=>{
        
        if(cur == l-1){
            min=Math.min(min,dst);
            return;
        }
        for(let i=cur;i<l;i++){ //这里i从cur起始，要不然就会超时
            if(arr[cur][i] != Infinity && !used[i]){
                used[i]=true;
                dfs(i, l, dst+arr[cur][i], arr, used);
                used[i]=false;
            }
        }
    }
    
    let dist=[];
    for(let i=0;i<n;i++){
        dist[i]=[];
        for(let j=0;j<n;j++){
            if(i==j){
                dist[i][j]=0;
            }
            else{
                dist[i][j]=Infinity;
            }
        }
    }
    graph.forEach(item => {

        dist[item[0]-1][item[1]-1]=Math.min(item[2],dist[item[0]-1][item[1]-1]);
        
    });
    
    let ud = [true];
    dfs(0,n,0,dist,ud);
    return min == Infinity ? -1 : min;
}

/**
 * 写法三：参考别人解题，一个动态规划的写法，这个写法最大的好处是不用去构建图，可通过，但是感觉这样可能会不太严谨，测试用例里没遍历到边可能正好不是最小值，所以能通过
 */
function findShortestPath( n ,  m ,  graph ) {

    
    let dp = [];
    dp[1] = 0;
    for(let i=2; i<n+1; i++){
        let min = Infinity;
        for(let j=0; j<m; j++){
            if(graph[j][1] == i){
                min = Math.min(min,graph[j][2]+dp[graph[j][0]] || Infinity);
            }
        }
        dp[i] = min;
    }
    return dp[n];
}