最短路径定义为所有的路径上的最长的一条:
可以通过堆维护所有的路径的最短【最短的定义对应的所有的路径的最长的一条】
堆优化版的dijkstra对应的最短路径的更新也对应的通过所有的路径的与当前路径的最长路径的进行更新
通过并查集的方式进行维护,最终的答案一定是已存在的所有的路径的一条,
通过依次将最短的路径添加到并查集中,如果对应的起点和终点联通,
则当前的路径及作为最短的路径,已经添加的所有的路径的最长一条
通过二分答案的方式+BFS判断对应的起点和重点之间是否可达
对于每一次二分答案,可以通过BFS判断是否可达
对于图最短路径的二分方式
class Solution {
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
public int minimumEffortPath(int[][] heights) {
int n=heights.length;
int m=heights[0].length;
int left=0;int right=999999;
while(left<right){
int mid=left+right>>1;
Queue<int[]> queue=new LinkedList<int[]>();
queue.offer(new int[]{0,0});
boolean[][] vis=new boolean[n][m];
for(int i=0;i<n;i++){
Arrays.fill(vis[i],false);
}
vis[0][0]=true;
while(!queue.isEmpty()){
int[] node=queue.poll();
for(int k=0;k<4;k++){
int a=node[0]+dx[k];
int b=node[1]+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&!vis[a][b]&&Math.abs(heights[a][b]-heights[node[0]][node[1]])<=mid){
vis[a][b]=true;
queue.offer(new int[]{a,b});
}
}
}
if(vis[n-1][m-1]){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
}
方式二:通过并查集的方式
所有的边都是通过从上往下或者从左往右的方式,所有的边权都是对应的相邻节点之间的节点绝对值
class Solution {
//通过并查集的方式进行维护
List<int[]> nums=new ArrayList<int[]>();
int[] father;
public int minimumEffortPath(int[][] heights) {
int n=heights.length;
int m=heights[0].length;
father=new int[m*n];
for(int i=0;i<father.length;i++){
father[i]=i;
}
//将所有的百年进行处理
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int id=i*m+j;
if(i>0){
//所有绝对值作为边权加入图中
nums.add(new int[]{id-m,id,Math.abs(heights[i-1][j]-heights[i][j])});
}
if(j>0){
nums.add(new int[]{id-1,id,Math.abs(heights[i][j-1]-heights[i][j])});
}
}
}
//将所有的边根据边权进行排序
Collections.sort(nums,(a,b)->a[2]-b[2]);
int res=0;
for(int i=0;i<nums.size();i++){
int[] node=nums.get(i);
int x=node[0];int y=node[1];int v=node[2];
father[find(x)]=find(y);
//判断是否起点和终点联通
if(find(0)==find(n*m-1)){
res=v;
break;
}
}
return res;
}
public int find(int x){
if(x!=father[x]){
father[x]=find(father[x]);
}
return father[x];
}
}
方式三:通过dijkstra方式进行最短路径
class Solution {
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
public int minimumEffortPath(int[][] heights){
//堆优化
int n=heights.length;int m=heights[0].length;
PriorityQueue<int[]> queue=new PriorityQueue<int[]>((a,b)->a[2]-b[2]);
queue.offer(new int[]{0,0,0});
//通过标记数组对每一个节点进行标记
boolean[] vis=new boolean[m*n];
//创建距离数组
int[] dist=new int[m*n];
Arrays.fill(dist,Integer.MAX_VALUE);
//起始点初始化
dist[0]=0;
while (!queue.isEmpty()) {
int[] node=queue.poll();
int x=node[0];int y=node[1];int weight=node[2];
if(vis[x*m+y]){
continue;
}
if(x==n-1&&y==m-1){
break;
}
vis[x*m+y]=true;
for(int k=0;k<4;k++){
int a=x+dx[k];
int b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&!vis[a*m+b]&&dist[a*m+b]>Math.max(weight,Math.abs(heights[a][b]-heights[x][y]))){
dist[a*m+b]=Math.max(weight,Math.abs(heights[a][b]-heights[x][y]));
queue.offer(new int[]{a,b,dist[a*m+b]});
}
}
}
return dist[m*n-1];
}
}