找到最大增益的最短路徑

Question

Problem link我該如何修改我的代碼，以便給我最大重量的最短路徑。

問題概述：我給出一個矩陣，我必須從一個索引轉到另一個索引最小的索引，每個索引都有一些增益，所以我必須找到最短路徑（如果有多條最短路徑可能，那麼路徑最大增益） 我的代碼：

public static int min(int x , int y ,int endx,int endy,int n ,int m,int[][] p){ 
    int[] dirx ={1,-1,0,0 }; 
     int[] diry={0,0,1,-1}; 
     LinkedList<Point> som = new LinkedList<Point>(); 
     som.add(new Point(x,y)); 
     //dp[x][y]=p[x][y]; 

     while(!som.isEmpty()){ 
      Point xx = som.pop(); 
      for(int i=0;i<4;i++){ 

       int x1 = xx.x + dirx[i]; 
       int y1 = xx.y + diry[i]; 

       if(x1>=0 && x1<n && y1>=0 && y1<m && p[x1][y1]!=-1 && dp[x1][y1]==-1){ 

        dp[x1][y1] = dp[xx.x][xx.y]+ 1; 
        som.add(new Point(x1,y1)); 

       } 
      } 

     } 

    return dp[endx][endy]; 
} 

Answer 1

從您的代碼添加

((dp[x1][y1]==-1) || ((dp[x1][y1] == dp[xx.x][xx.y] + 1) && (w[xx.x][xx.y]+p[x1][y1] > w[x1][y1]))) 

，而不是

(dp[x1][y1]==-1) 

和條件

w[x1][y1] = w[xx.x][xx.y] + p[x1][y1]; 

這意味着，如果你發現了同樣的長度

你也可以優化不添加相同點幾次的更好的方法，你會更新路徑的結果，但我認爲這裏面在這個特定的問題中沒有必要

Answer 2

這個問題可以用Dijkstra算法來解決。但是我們需要在原始算法中比較距離和增益量，而不僅僅是距離。

這些是我的一些代碼提示，所以你只需要改變你的代碼的一部分。

class Entry implements Comparable<Entry>{ 
    int x,y, dist, gain; 
    //Constructor is omitted. 
    public int compareTo(Entry o){ 
     if(dist != o.dist)//Compare distance first 
      return dist - o.dist; 
     return o.gain - gain;//Compare gain value 
    } 
} 

//Method signature is omitted 
PriorityQueue<Entry> q = new PriorityQueue(); 
q.add(new Entry(0,0,0,gain[0][0]); 
int[][][]dist = new int[n][m][2];//Assume size of matrix is n x m 
//Init dist array omitted 
dist[0][0][0] = 0;//Init distance 
dist[0][0][1] = gain[0][0];//Init gain amount, assume we have a gain matrix 
while(!q.isEmpty()){ 
    Entry e = q.poll(); 
    if(dist[e.x][e.y][0] == e.dist && dist[e.x][e.y][1] == e.gain){ 
     for(all valid next positions (a,b)) 
      if(dist[a][b][0] > e.dist + 1 || (dist[a][b][0] == e.dist + 1 && dist[a][b][1] < e.gain + gain[a][b]){ 
       //Notice the condition to update the dist array 
       dist[a][b][0] = e.dist + 1; 
       dist[a][b][1] = e.gain + gain[a][b]; 
       q.add(new Entry(a,b,e.dist + 1, e.gain + gain[a][b]); 
      } 
    } 
} 
return dist[n-1][m-1][1];