• 文章目录题目描述题目解读思路一： 队列优化迪杰斯特拉传统迪杰斯特拉队列优化的迪杰斯特拉python 自带的堆排序 与 list.sort()上代码思路二：并查集 题目描述 题目解读 思路一： 队列优化迪杰斯特拉 传统迪杰...

@author=YHR | 转载请标明来源

文章目录题目描述题目解读思路一： 队列优化迪杰斯特拉传统迪杰斯特拉队列优化的迪杰斯特拉python 自带的堆排序  与 list.sort()本题解读 & 代码思路二：并查集上代码先

题目描述
题目解读
思路一： 队列优化迪杰斯特拉
传统迪杰斯特拉
队列优化的迪杰斯特拉
python 自带的堆排序  与 list.sort()
本题解读 & 代码
class Solution:
def __init__(self):
self.inf = int(1e6 + 1)

def minimumEffortPath(self, heights):
self.rows = len(heights)
if self.rows > 0:
self.cols = len(heights[0])
if self.cols > 0:
aim = self.rows * self.cols - 1
start = 0
Dist = self.Dijstra(heights, start)
return Dist[aim]

return 0


def getRowAndColByIndex(self, index):
row = index // self.cols
col = index % self.cols

return row, col



def Dijstra(self, heights, start):
totalNodesNum = self.rows * self.cols

dir = [[0, -1], [0, 1], [-1, 0], [1, 0]]
hasSeen = [0] * totalNodesNum  # 0表示未遍历，1表示已经纳入了遍历

# intial the distance from start to others
Dist = [self.inf] * totalNodesNum;
Dist[start] = 0
import heapq
# initial the sorted queue
candidate = []
heapq.heapify(candidate)
heapq.heappush(candidate, [Dist[start], start])

while len(candidate) > 0:
[Dist2nownode, nownode] = heapq.heappop(candidate)

if hasSeen[nownode] == 1:
continue
else:
hasSeen[nownode] = 1

now_r, now_c = self.getRowAndColByIndex(nownode)
for _ in range(4):
new_r = now_r + dir[_][0]
new_c = now_c + dir[_][1]

if 0 <= new_r < self.rows and 0 <= new_c < self.cols:
if hasSeen[new_r * self.cols + new_c] != 1:
if Dist[new_r * self.cols + new_c] > max(Dist2nownode,
abs(heights[now_r][now_c] - heights[new_r][new_c])):
Dist[new_r * self.cols + new_c] = max(Dist2nownode,
abs(heights[now_r][now_c] - heights[new_r][new_c]))
heapq.heappush(candidate, [Dist[new_r * self.cols + new_c], new_r * self.cols + new_c])

return Dist

思路二：并查集
上代码先
import heapq
class Solution:
def __init__(self):
self.inf = int(1e6 + 1)

def minimumEffortPath(self, heights):
self.rows = len(heights)
if self.rows > 0:
self.cols = len(heights[0])
if self.cols > 0:
self.totalNodeNums = self.rows * self.cols
return self.unionAndSearchWithKruskal(heights, self.totalNodeNums-1)
return 0

def getRowAndColByIndex(self, index):
row = index // self.cols
col = index % self.cols

return row, col

def getEdges(self, heights):
edges = []
heapq.heapify(edges)  # sort by element 0, small heap
# kruskal 获取边
for _ in range(self.totalNodeNums):
this_r, this_c = self.getRowAndColByIndex(_)
# 获取到右边 边
if this_c < self.cols-1:
next_r , next_c = this_r, this_c+1
heapq.heappush(edges, [abs(heights[next_r][next_c] - heights[this_r][this_c]), _, next_r*self.cols + next_c])

# 获取到下面 边
if this_r < self.rows-1:
next_r , next_c = this_r+1, this_c
heapq.heappush(edges, [abs(heights[next_r][next_c] - heights[this_r][this_c]), _, next_r*self.cols + next_c])

return edges

def findRoot(self, parentDict, node):
parent = parentDict[node]
while parent != node:
node = parent
parent = parentDict[node]
return parent

def unionAndSearchWithKruskal(self, heights, aim):
parentDict = [_ for _ in range(self.totalNodeNums)]
size = [1]*self.totalNodeNums
candidate_edges = self.getEdges(heights)
if len(candidate_edges) == 0:
return 0
while len(candidate_edges) > 0:
[edgeweight, startId, endId] =  heapq.heappop(candidate_edges)

start_parent = self.findRoot(parentDict, startId)
end_parent = self.findRoot(parentDict, endId)

if start_parent != end_parent:
# 没有成环才考虑加入边
if size[start_parent] < size[end_parent]:
start_parent, end_parent = end_parent, start_parent
parentDict[end_parent] = start_parent
size[start_parent] += size[end_parent]  # !!!! 易错点1， 算人头，是把对方麾下的人头都算进来
if self.findRoot(parentDict, aim) ==  self.findRoot(parentDict, 0):
#  # !!!! 易错点2  比较联通是比较他俩祖先是否一样，有可能0的祖先是别人呢！！！！
return edgeweight  # 直接返回weight就可以，因为边是从小到大排序，加入这条边，他俩才联通，说明这条边是必须边！




展开全文
• 有 N 个网络节点，标记为 1 到 N。 给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。...
有 N 个网络节点，标记为 1 到 N。
给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
示例：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
输出：2
代码
class Solution {
HashMap<Integer, List<int[]>> map;HashMap<Integer,Integer> dist;
public int networkDelayTime(int[][] times, int N, int K) {
dist=new HashMap<>();
map=new HashMap<>();
boolean[] check=new boolean[N+1];
for(int[] time:times)//构造邻接表
{    if(!map.containsKey(time[0]))
map.put(time[0], new ArrayList<int[]>());
}

for(int i=1;i<=N;i++)
dist.put(i,Integer.MAX_VALUE);
dist.put(K,0);
while (true)
{
int curDist=Integer.MAX_VALUE;
int curNode=-1;
for(int i=1;i<=N;i++)
if(!check[i]&&dist.get(i)<curDist)//找出当前距离起点的最近的节点
{
curDist=dist.get(i);
curNode=i;

}
if(curNode<0) break;//遍历完了所有节点
check[curNode]=true;//当前节点已经被访问
if(map.containsKey(curNode))
{
for(int[] next:map.get(curNode))//更新邻接点与起点的最小距离
dist.put(next[0], Math.min(next[1]+dist.get(curNode),dist.get(next[0])));
}

}
int cnt=0;
for(int c:dist.values())//遍历所有的节点到起点的距离
{   if(c==Integer.MAX_VALUE) return -1;
cnt= Math.max(c,cnt);}
return cnt;

}
}

堆实现代码
    HashMap<Integer, List<int[]>> map;
public int networkDelayTime(int[][] times, int N, int K) {
HashMap<Integer,Integer> dist=new HashMap<>();
map=new HashMap<>();
boolean[] check=new boolean[N+1];
for(int[] time:times)//构造邻接表
{    if(!map.containsKey(time[0]))
map.put(time[0], new ArrayList<int[]>());
}
PriorityQueue<int[]> priorityQueue=new PriorityQueue<>(((o1, o2) -> o1[0]-o2[0]));//按距离从小到大
priorityQueue.offer(new int[]{0,K});//将起点加入优先队列
while (!priorityQueue.isEmpty())
{
int[] temp=priorityQueue.poll();
int d=temp[0],node=temp[1];
if(dist.containsKey(node)) continue;//已经确定了距离的不再访问
dist.put(node,d);
if(map.containsKey(node))
for(int[] next:map.get(node))//将邻接点到起点的距离加入优先队列
{ if(!dist.containsKey(next[0]));
{

priorityQueue.offer(new int[]{d+next[1],next[0]});}}
}if(dist.size()!=N) return -1;
int cnt=0;
for(int c:dist.values())
{
cnt= Math.max(c,cnt);}
return cnt;
}



展开全文
• class Solution { boolean[][] vis; int[][] g; int[] dx = {0,1,0,-1}; int[] dy = {1,0,-1,0}; int m,n; public int minimumEffortPath(int[][] heights) { g = heights; int l = 0,r = (int)1e6;...
1631. 最小体力消耗路径
此题做法非常多，主要有二分的做法、最短路的做法。

二分+深度优先搜索

class Solution {
boolean[][] vis;
int[][] g;
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
int m,n;

public int minimumEffortPath(int[][] heights) {
g = heights;
int l = 0,r = (int)1e6;
m = g.length;
n = g[0].length;
while(l<r){
int mid = l+(r-l)/2;
vis = new boolean[110][110];
if(dfs(0,0,mid)){
r = mid;
}else{
l = mid+1;
}
}
return l;
}

boolean dfs(int x,int y,int max){
vis[x][y] = true;
if(x == m-1 && y == n-1){
return true;
}
for(int k=0;k<4;k++){
int nx = x + dx[k];
int ny = y + dy[k];
if(nx>=0 && nx<m && ny>=0 && ny<n){
int cost = Math.abs(g[x][y] - g[nx][ny]);
if(!vis[nx][ny] && cost <= max ) {
if(dfs(nx,ny,max)) return true;
}
}
}
return false;
}
}



展开全文
•  最短路径的常用解法有迪杰斯特拉算法Dijkstra Algorithm, 弗洛伊德算法Floyd-Warshall Algorithm, 和贝尔曼福特算法Bellman-Ford Algorithm，其中，Floyd算法是多源最短路径，即求任意点到任意点到最短路径，而...

最短路径求解

最短路径的常用解法有迪杰克斯特拉算法Dijkstra Algorithm, 弗洛伊德算法Floyd-Warshall Algorithm, 和贝尔曼福特算法Bellman-Ford Algorithm，其中，Floyd算法是多源最短路径，即求任意点到任意点到最短路径，而Dijkstra算法和Bellman-Ford算法是单源最短路径，即单个点到任意点到最短路径。
单源最短路径(无负权值)：

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

代码实现

// AllTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <stack>
using namespace std;
#define INT_MAX1 999999
typedef struct MGraph
{
int n,line;
int m[100][100];
}gg,*pG;
// g -- adjacent matrix pointer
// v0 -- the source node
// dist[] -- the distance from the ith node to the source node
// prev[] -- the previous node of the ith node
void Dijkstra (pG g,int *pre,int *dis,int v0)
{
bool visited[100];  // 判断是否已存入该点到S集合中
int n=g->n;
for (int i=1;i<=n;i++)
{
dis[i]=g->m[v0][i]; //初始dis
visited[i]=false;  // 初始都未用过该点
if (dis[i]==INT_MAX1)  //初始pre
pre[i]=0;
else
pre[i]=v0;
}
visited[v0]=true; //初始起点
dis[v0]=0;
// 依次将未放入S集合的结点中，取dis[]最小值的结点，放入结合S中
// 一旦S包含了所有V中顶点，dis就记录了从源点到所有其他顶点之间的最短路径长度
// 注意是从第二个节点开始，第一个为源点
for (int i=2;i<=g->n;i++) //1
{
int u=v0,min=INT_MAX1;
// 找出当前未使用的点j的dis[j]最小值
for (int j=1;j<=g->n;j++) //
if (!visited[j]&&dis[j]<min)
{
u=j; // u保存当前邻接点中距离最小的点的号码
min=dis[j];
}
visited[u]=true;
dis[u]=min;//其实这个不需要再赋值
//更新dis
for (int j=1;j<=g->n;j++)
if (!visited[j]&&g->m[u][j]<INT_MAX1&&dis[u]+g->m[u][j]<dis[j])
{
pre[j]=u;
dis[j]=dis[u]+g->m[u][j];
}
}

}
// 查找从源点v到终点u的路径，并输出
void research(pG g,int *pre,int v0,int u)
{
int t=pre[u];
stack<int> s;
s.push(u);
while (t!=v0)
{
s.push(t);
t=pre[t];
}
s.push(v0);
while (!s.empty())
{
int output=s.top();
s.pop();
if (output==v0)
cout<<v0;
else
cout<<"->"<<output;
}
}
int main()
{
MGraph g;
freopen("input.txt","r",stdin);
cin>>g.n;
cin>>g.line;
for (int i=1;i<=g.n;i++)
for (int j=1;j<=g.n;j++)
g.m[i][j]=INT_MAX1;
int dis[100];
generate(dis,dis+100,[](){return INT_MAX1;});
int pre[100];
generate(pre,pre+100,[](){return 1;});
for (int i=1;i<=g.line;i++)
{
int x,y,weight;
cin>>x>>y>>weight;
g.m[x][y]=weight;
//g.m[y][x]=weight;//无向图
}
for(int i=1; i<=g.n; ++i)
{
for(int j=1; j<=g.n; ++j)
printf("%8d", g.m[i][j]);
printf("\n");
}
Dijkstra(&g,pre,dis,1);
cout<<"源点到最后一个顶点的最短路径长度: "<< dis[g.n] << endl;
// 路径
cout << "源点到最后一个顶点的路径为: ";
research(&g,pre,1,g.n);
return 0;
}    
数据
5
7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
单源最短路径(有负权值)

任意两点最短路径
LeetCode 743. Network
Delay Time

Desciption

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i]
= (u, v, w), where u is the source node, v is
the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal?
If it is impossible, return -1.

Note:
N will be in the range [1,
100].K will be in the range [1,
N].The length of times will be in the range [1,
6000].All edges times[i] = (u, v, w) will have 1
<= u, v <= N and 1 <= w <= 100.解题思路：

基于Bellman-Ford算法的解法，时间复杂度是O(VE)，V和E分别是结点和边的个数。这种算法是基于DP来求全局最优解，原理是对图进行V
- 1次松弛操作，这里的V是所有结点的个数（为啥是V-1次呢，因为最短路径最多只有V-1条边，所以只需循环V-1次），在重复计算中，使得每个结点的距离被不停的更新，直到获得最小的距离，这种设计方法融合了暴力搜索之美，写法简洁又不失优雅。之前提到了，Bellman-Ford算法可以处理负权重的情况，但是不能有负环存在，一般形式的写法中最后一部分是检测负环的，如果存在负环则报错。不能有负环原因是，每转一圈，权重和都在减小，可以无限转，那么最后的最小距离都是负无穷，无意义了。没有负环的话，V-1次循环后各点的最小距离应该已经收敛了，所以在检测负环时，就再循环一次，如果最小距离还能更新的话，就说明存在负环。这道题由于不存在负权重，所以就不检测了。

class Solution {
public://最短路径中的最大值
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
vector<int> dist(N+1,INT_MAX);
dist[K]=0;
for (int i=1;i<N;++i)
for (auto e:times){
int u=e[0],v=e[1],w=e[2];
if (dist[u]!=INT_MAX&&dist[u]+w<dist[v])//update edge of u vertex
dist[v]=dist[u]+w;
}
int max=0;
for (int i=1;i<=N;++i)
max=(dist[i]>max?dist[i]:max);
return max==INT_MAX?-1:max;
}
};

参考网址：http://developer.51cto.com/art/201105/262210.htm


展开全文
• class Solution { public: int countRestrictedPaths(int n, vector<vector<int>>& edges) { // 建图，迪杰斯特拉 求解 每个节点到 n 的最短距离 dis vector,int>> g(n); for(auto & e : edges) { g[e[0]-1][e[1]-1...
• 算法-并查集/堆/Dijkstra迪杰斯特拉-水位上升的泳池中游泳 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/swim-in-rising-water/ 1.2 题目描述 2 并查集 2.1 思路 注意，平台数字是连续的，且从0到nn-...
• public class Leetcode { public static void main(String args[]) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); int m=scan.nextInt(); int s=scan.nextInt(); int cost...
• 最近刷leetcode，两周刷了接近80道题，勉强算是入门了，不过感觉一些除了一些...迪杰斯特拉算法（Dijkstra） void dijkstra(MGraph G, int v) { int dist[MAXSIZE]; //dist[i]:源点到点 i 的路径长度 int path[MAXSIZ
• 迪杰斯特拉算法
• 迪杰斯特拉Dijkstra 图论问题一般分为： 单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径 最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径 （有向）无权图 （有向）有权图 ...
• Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space? Subscribe to see which companies asked this ...思路：迪杰斯特拉环算法/** * Defini
• 迪杰斯特拉最短路径问题 class Solution { public: int res; void djs(vector<vector<int>>& node,int k,vector<int>& visit) { int N=node.size(); visit[k]=1;...
• 思路：迪杰斯特拉最短路径应用到该题，初步思想：将每个空格看作每个节点，相邻的节点之间存在边，边的权值为相邻值的高度差，求左上角到右下角的最小体力消耗，即为类似求原点到终点的路径。（会超越时间限制） ...
• 起初分析题目，题意就是要求左上角到左下角的路径和，也就是单元最短路径，开始就想着用迪杰斯特拉来求，但是仔细看了一下说明，每次只能向下或者向右移动，也就是说它这个和迪杰斯特拉求算法不一样，这个要...
• 通过迪杰斯特拉最短路径算法，求出从节点K出发到每一个节点的最短路径。其中最大值的就是所求结果，若有节点从未被访问过则返回-1。 class Solution { public: typedef struct Dest { Dest(int d, int w) :...
• 变相的迪杰斯特拉算法。 class Solution: def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float: degree = collections.defaultdict(dict) for ...
• 这是LeetCode上的一道题，给定一张图，寻找概率最大的路径。... // 迪杰斯特拉算法解决,用BFS+优先级队列实现 public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) { Li
• ## leetcode-542-01 Matrix

千次阅读 2017-04-11 11:22:41
因为这道题是求值为1的点到值为0的区域的最短距离，因为是在图上求最短距离，所以可以用广度优先搜索方法求解，该方法在求最小生成树和迪杰斯特拉最短路径算法的思想中都有体现。本质上是有一个已知最优路线（最优...
• 图的知识点有很多，刚开始有图的存储结构，图的DFS和图的BFS遍历，最小生成树（prime算法和克鲁斯卡尔算法），有向无环图的应用，拓扑排序，关键路径和最短路径（迪杰斯特拉算法和弗洛伊德算法）。 上面这些关于这些...
• 使用迪杰斯特拉算法的思想，对其进行变化，改为：每次选一个当前可选的最小的边，当右下角那个点被遍历时，结束程序。 刚开始只有(0,1)和(1,0)位置的点是可以选的，于是将它们加入到待遍历的点集合里。 每次从待遍历...
• leetcode中图的算法 克鲁斯卡尔算法（无向图） 用于最小生成树的计算： n个点 找到n-1个边 边的权重和最小 思路： ...迪杰斯特拉算法（有向图） 用于计算单源点到某一点的最短路径问题，无负权边 思路：
• Dijkstra.java，迪杰斯特拉算法。 DnGraphTopologic.java，图的拓扑排序。 Dnf.java。娱乐写的小文字游戏。 Empress.java，八皇后问题。 GCD.java 。最大公约数算法 GetPosition.java String[], 给你两个 字母 A，B...