在一个有 n 个点, m 个边的有向图中,已知每条边长,求出 1 到 n 的最短路径,返回 1 到 n 的最短路径值。如果 1 无法到 n ,输出 -1
图中可能有重边,无自环。
数据范围: , ,
5,5,[[1,2,2],[1,4,5],[2,3,3],[3,5,4],[4,5,5]]
9
2,1,[[1,2,4]]
4
两个整数n和m,表示图的顶点数和边数。一个二维数组,一维3个数据,表示顶点到另外一个顶点的边长度是多少每条边的长度范围[0,1000]。
注意数据中可能有重边
using PII = pair<int, int>; const int INF = 0x3f3f3f3f; class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int 顶点数 * @param m int 边数 * @param graph intvector<vector<>> 一维3个数据,表示顶点到另外一个顶点的边长度是多少 * @return int */ int findShortestPath(int n, int m, vector<vector<int> >& edges) { vector<vector<PII>> g(n + 1); for (const auto& e : edges) g[e[0]].emplace_back(e[1], e[2]); return dijkstra_algorithm(g, n); } private: // 堆优化版的dijkstra算法,适用于 sparse graph(稀疏图) int dijkstra_algorithm(vector<vector<PII>>& g, const int n) { vector<int> seen(n + 1, 0); vector<int> dists(n + 1, INF); dists[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> q; q.emplace(0, 1); while (not q.empty()) { const auto [dist, cur] = q.top(); q.pop(); if (seen[cur]++) continue; for (const auto [nxt, w] : g[cur]) if (dist + w < dists[nxt]) { dists[nxt] = dist + w; q.emplace(dist + w, nxt); } } return dists[n]; } };
class Solution: def __init__(self): # 哈希表构造图中边信息 self.map = {} # 记录最短路径长度 self.result = float('INF') def findShortestPath(self , n , m , graph ): # 先构图 for g in graph: if g[0] in self.map: # 重边保留最小的长度 注:长度上限为1000 self.map[g[0]][g[1]] = min(g[2],self.map[g[0]].get(g[1],1001)) else: self.map[g[0]] = {g[1]:g[2]} # 1为起点 n为终点 self.dfs(1, n, 0) return self.result if self.result != float('INF') else -1 # 深度优先遍历 def dfs(self, start, end, val): if start == end: # 有效路径 记录最小值 self.result = min(self.result, val) return # 不存在的结点即为无效路径 if start not in self.map: return # 查找路径 即找start所有的下个结点 for nex in self.map[start].keys(): self.dfs(nex, end, val + self.map[start][nex])python 动态规划
class Solution: def findShortestPath(self , n , m , graph ): # dp[i]定义为到达结点i的最小路径长度 dp = [-1] * (n+1) # basecase 起点即终点 dp[1] = 0 # 状态转移 for i in range(2, n+1): # 记录到达每个结点最小路径长度 min_len = float('INF') # 遍历所有边信息 for j in range(m): # 是否有边到达结点i 且 该边的起点是否可达 if graph[j][1] == i and dp[graph[j][0]] != -1: min_len = min(min_len, graph[j][2] + dp[graph[j][0]]) # 判断是否有有效路径到达结点i if min_len != float('INF'): dp[i] = min_len # 返回到达终点n的最小路径长度 return dp[n]
#include <string> #include <vector> #include <algorithm> #include <unordered_map> #include <queue> #include <stack> using namespace std; class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int 顶点数 * @param m int 边数 * @param graph intvector<vector<>> 一维3个数据,表示顶点到另外一个顶点的边长度是多少 * @return int */ const int INF = 0x3f3f3f3f; int n; int findShortestPath(int _n, int m, vector<vector<int> >& graph) { // write code here // dijkstra 算法 n = _n; vector<vector<int>> g(n+1, vector<int>(n+1, INF)); for(auto &x: graph){ int a = x[0], b = x[1], c = x[2]; g[a][b] = min(g[a][b], c); //处理重边 } return dijkstra(g, 1, n); } int dijkstra(vector<vector<int>> &g, int start, int end){ vector<int> d(n+1, INF); vector<int> st(n+1); d[start] = 0; for(int i = 1; i <= n; i++){ int t = -1; for(int j = 1; j <= n; j++){ if(!st[j] && (t==-1 || d[t] > d[j])) t = j; } if(t == -1) return -1; st[t] = 1; for(int i = 1; i <= n; i++){ if(!st[i]) d[i] = min(d[i], g[t][i] + d[t]); } } return d[end]; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int 顶点数 * @param m int 边数 * @param graph int二维数组 一维3个数据,表示顶点到另外一个顶点的边长度是多少 * @return int */ public int findShortestPath (int n, int m, int[][] graph) { // write code here int[] distanceArr = new int[n + 1]; Arrays.fill(distanceArr, Integer.MAX_VALUE); boolean[] visited = new boolean[n + 1]; distanceArr[1] = 0; // 自己到自己的距离是0 visited[1] = true; // 自己走过了 for(int i = 2; i <= n; i++){ // 计算1到每个点的最短路 for(int j = 0; j < graph.length; j++){ int from = graph[j][0], to = graph[j][1], edge = graph[j][2]; if(visited[from] && to == i){ distanceArr[to] = Math.min(distanceArr[to], distanceArr[from] + edge); visited[to] = true; } } } return distanceArr[n] == Integer.MAX_VALUE ? -1: distanceArr[n]; } }
import java.util.*; public class Solution { /** * 需要注意重复方向的边,取最短的那条;其次是有些点是不连通的。 * * * @param n int 顶点数 * @param m int 边数 * @param graph int二维数组 一维3个数据,表示顶点到另外一个顶点的边长度是多少 * @return int */ public static int findShortestPath(int n, int m, int[][] graph) { int row = m; boolean[] mark = new boolean[row]; int[] dp = new int[n + 1]; dp[1] = 0; for (int i = 2; i <= n; i++) { dp[i] = -1; } for (int i = 2; i <= n; i++) { for (int j = 0; j < row; j++) { if (!mark[j]) { if (graph[j][1] == i) { if (dp[i] == -1) { if (dp[graph[j][0]] != -1) { dp[i] = dp[graph[j][0]] + graph[j][2]; } } else { if (dp[graph[j][0]] != -1) dp[i] = Math.min(dp[graph[j][0]] + graph[j][2], dp[i]); } mark[j] = true; } } } } return dp[n]; } }
public int findShortestPath (int n, int m, int[][] graph) { final int INF = Integer.MAX_VALUE / 2; int[] dp = new int[n]; Arrays.fill(dp, INF); dp[0] = 0; // 重写排序 // 按照起始节点序号升序->距离升序->结束节点升序 进行排序 Arrays.sort(graph, new Comparator<int[]>(){ @Override public int compare(int[] num1, int[] num2){ if (num1[0] != num2[0]){ return num1[0] - num2[0]; }else if (num1[2] != num2[2]){ return num1[2] - num2[2]; }else{ return num1[1] - num2[1]; } } }); for (int[] temp : graph) { // x为起始节点, y为结束节点, dis为x->y的有向距离 int x = temp[0] - 1; int y = temp[1] - 1; int dis = temp[2]; if (dp[x] + dis < dp[y]) { dp[y] = dp[x] + dis; } } return dp[n-1] == INF ? -1 : dp[n-1]; }
import java.util.*; public class Solution { public int findShortestPath (int n, int m, int[][] graph) { int [] visited = new int[n]; int [][] myGraph = new int[n][n]; int[] dp = new int[n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ myGraph[i][j] = Integer.MAX_VALUE; } myGraph[i][i] = 0; dp[i] = Integer.MAX_VALUE; } for(int i=0;i<graph.length;i++){ myGraph[graph[i][0]-1][graph[i][1]-1] = Math.min(graph[i][2],myGraph[graph[i][0]-1][graph[i][1]-1]); myGraph[graph[i][1]-1][graph[i][0]-1] = Math.min(graph[i][2],myGraph[graph[i][1]-1][graph[i][0]-1]); } dp[0] = 0; while(true){ int index = findMinIndex(visited,dp); if(index == -1){ break; } visited[index] = 1; for(int j=0;j<n;j++){ if( myGraph[index][j] != Integer.MAX_VALUE ){ dp[j] = Math.min(dp[index] + myGraph[index][j],dp[j]); } } } if(dp[n-1]!=Integer.MAX_VALUE){ return dp[n-1]; }else{ return -1; } } int findMinIndex(int [] visited,int [] dp){ int len = dp.length; int min = Integer.MAX_VALUE; int minIndex = -1; for(int i=0;i<len;i++){ if(dp[i] < min && visited[i]==0){ min = dp[i]; minIndex = i; } } return minIndex; } }
// dijkstra, 吐槽一点模拟面试不给数据范围 #include <cstring> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int 顶点数 * @param m int 边数 * @param graph intvector<vector<>> 一维3个数据,表示顶点到另外一个顶点的边长度是多少 * @return int */ int dist[1010], st[1010], g[1010][1010]; int findShortestPath(int n, int m, vector<vector<int> >& graph) { // write code here memset(dist, 0x3f, sizeof dist); for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) if(i == j) g[i][j] = 0; else g[i][j] = 0x3f3f3f3f; for(auto e : graph) { g[e[0]][e[1]] = min(g[e[0]][e[1]], e[2]); } dist[1] = 0; for(int i = 0; i < n; i ++) { int t = -1; for(int j = 1; j <= n; j ++) if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j; st[t] = 1; for(int j = 1; j <= n; j ++) { dist[j] = min(dist[j], dist[t] + g[t][j]); } } if(dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int 顶点数 * @param m int 边数 * @param graph int二维数组 一维3个数据,表示顶点到另外一个顶点的边长度是多少 * @return int */ public int findShortestPath (int n, int m, int[][] graph) { int[][] edge = new int[n+1][n+1]; int inf = Integer.MAX_VALUE/2; for(int i = 1;i<=n;i++){ Arrays.fill(edge[i],inf); } for(int i = 0;i<m;i++){ edge[graph[i][0]][graph[i][1]] = Math.min(graph[i][2],edge[graph[i][0]][graph[i][1]]); } int[] dist = new int[n+1]; Arrays.fill(dist,-1); for(int i = 2;i<=n;i++){ dist[i] = edge[1][i]; } boolean[] used = new boolean[n+1]; dist[1] = 0; used[1] = true; for(int i = 1;i<n;i++){ int minDist = Integer.MAX_VALUE; int minIndex = 1; for(int j = 2;j<=n;j++){ if(!used[j] && dist[j] != -1 && dist[j]<minDist){ minDist = dist[j]; minIndex = j; } } used[minIndex] = true; for(int j = 1;j<=n;j++){ if(edge[minIndex][j]!=inf){ if(dist[j]!=-1) dist[j] = Math.min(dist[j],dist[minIndex]+edge[minIndex][j]); else dist[j] = dist[minIndex]+edge[minIndex][j]; } } } return dist[n]; // write code here } }
public int findShortestPath(int n, int m, int[][] graph) { int[] dp = new int[n + 1]; // dp[i] 表示到达 i 结点的最短长度 int[][] roads = new int[n+1][n+1]; for (int i = 0; i < m; ++i) { int s = graph[i][0]; int e = graph[i][1]; int len = graph[i][2]; if (roads[s][e] == 0) { roads[s][e] = len; } else { roads[s][e] = Math.min(roads[s][e], len); } } dp[1] = 0; for (int i = 2; i <= n; ++i) { int minLen = Integer.MAX_VALUE; for (int j = 1; j <= i - 1; ++j) { // 该结点是可达的才行 int sLen = dp[j]; if (sLen != -1) { int len = roads[j][i]; if (0 != len) { minLen = Math.min(minLen, sLen + len); } } } dp[i] = minLen == Integer.MAX_VALUE ? -1 : minLen; } return dp[n]; }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int 顶点数 * @param m int 边数 * @param graph intvector<vector<>> 一维3个数据,表示顶点到另外一个顶点的边长度是多少 * @return int */ typedef struct { int num; int sum; }dot; int findShortestPath(int n, int m, vector<vector<int> >& graph) { // write code here vector <vector<int>> g(n+1,vector<int>(n+1,1e6)); for(int i=0;i<graph.size();i++) { int from=graph[i][0],end=graph[i][1],w=graph[i][2]; g[from][end]=min(g[from][end],w); } //1e5表示无边 queue <dot> queue; queue.push((dot){1,0}); int res=1e6; while(!queue.empty()) { dot t=queue.front(); queue.pop(); if(t.sum>=res) continue; if(t.num==n) { res=min(res,t.sum); continue; } for(int i=1;i<=n;i++) { if(g[t.num][i]!=1e6) { dot temp; temp.num=i; temp.sum=t.sum+g[t.num][i]; queue.push(temp); } } } return res==1e6?-1:res; } };
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @param n int 顶点数 * @param m int 边数 * @param graph int二维数组 一维3个数据,表示顶点到另外一个顶点的边长度是多少 * @return int */ private int min = Integer.MAX_VALUE; public int findShortestPath (int n, int m, int[][] graph) { int[][] dp = new int[n][n]; for(int[] d : dp){ Arrays.fill(d , Integer.MAX_VALUE); } // 构造图 for(int[] edge : graph){ // 题目有个大坑,就是说可能有重复边,所以在构造边图的时候需要进行一个比较 // (dp[edge[0] - 1][edge[1] - 1] = Math.min(edge[2] , dp[edge[0] - 1][edge[1] - 1]);) // 则不是直接赋值(dp[edge[0] - 1][edge[1] - 1] = edge[2];) dp[edge[0] - 1][edge[1] - 1] = Math.min(edge[2] , dp[edge[0] - 1][edge[1] - 1]); } boolean[] used = new boolean[n]; used[0] = true; dfs(0 , n , 0 , dp , used); return min == Integer.MAX_VALUE ? -1 : min; } public void dfs(int curr ,int n , int dst , int[][] graph ,boolean[] used){ if(curr == n - 1){ min = Math.min(min , dst); return ; } for(int i = 0 ; i < n ; i ++){ // 如果有边可达,并且该点还没被使用 if(graph[curr][i] != Integer.MAX_VALUE && !used[i]){ used[i] = true; dfs(i , n , dst + graph[curr][i] , graph , used); used[i] = false; } } } }
python3动态规划
from collections import defaultdict class Solution: def findShortestPath(self , n , m , graph): nexts = defaultdict(list) for src, dst, w in graph: nexts[src].append((dst, w)) dp = [None] * (n) + [0] # d[k]表示k到n的最短距离 for i in range(n, 0, -1): if any(dp[j] is not None for j, _ in nexts[i]): dp[i] = min(dp[j] + w for j, w in nexts[i] if dp[j] is not None) return dp[1] if dp[1] else -1
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param n int 顶点数 # @param m int 边数 # @param graph int二维数组 一维3个数据,表示顶点到另外一个顶点的边长度是多少 # @return int # class Solution: def findShortestPath(self, n, m, graph): # write code here headMap = dict() # n = len(graph) points = dict() scores = [-1 for i in range(n+1)] paths = dict() matrix = [[-1 for j in range(n+1)] for i in range(n+1)] for g in graph: headMap[g[0]] = float("inf") headMap[g[1]] = float("inf") x, y = g[0], g[1] if x not in points: points[x] = [] points[x].append(y) if matrix[x][y] == -1: matrix[x][y] = g[2] elif matrix[x][y] > g[2]: matrix[x][y] = g[2] paths[1] = None scores[1] = 0 headMap[1] = 0 while len(headMap) > 0: k = self.getSmallDict(headMap) scores[k] = headMap[k] headMap.pop(k) for p in points.get(k, []): if p in headMap : if scores[k] + matrix[k][p] < headMap[p]: paths[p] = k headMap[p] = min(scores[k] + matrix[k][p], headMap[p]) return scores[n] def getSmallDict(self, h): kk = 0 value = float("inf") for k in h: if kk == 0: kk = k if h[k] < value: value = h[k] kk = k return kk
bfs广度优先
public int findShortestPath (int n, int m, int[][] graph) { // write code here List> list = new ArrayList(); for (int i = 0; i < n; i++) { List childList = new ArrayList(); list.add(childList); } for (int[] value : graph) { if(value[1] == value[0]) { continue; } list.get(value[0] - 1).add(value); } int[] arr = new int[n]; Arrays.fill(arr, Integer.MAX_VALUE); arr[0] = 0; Queue queue = new LinkedList(); queue.add(1); while(!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { Integer poll = queue.poll(); List ints = list.get(poll -1); for (int j = 0; j < ints.size(); j++) { if(arr[ints.get(j)[0]-1] + ints.get(j)[2] < arr[ints.get(j)[1]-1]){ arr[ints.get(j)[1] -1] = arr[ints.get(j)[0]-1] + ints.get(j)[2]; queue.add(ints.get(j)[1]); } } } } return arr[n-1] == Integer.MAX_VALUE ? -1 : arr[n-1]; }
int findShortestPath(int n, int m, vector<vector<int> >& graph) { // write code here int l0=0; for(int i=0;i<m;i++){ int l=0; if(graph[i][1]==n){ if(graph[i][0]==1){ l=graph[i][2]; if(l0==0){ l0=l; } else{ if(l0>l){ l0=l; } } } int l1=findShortestPath(graph[i][0],m ,graph ); if(l1!=0){ l=graph[i][2]+l1; if(l0==0){ l0=l; } else{ if(l0>l){ l0=l; } } } } } return l0; }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param n int 顶点数 # @param m int 边数 # @param graph int二维数组 一维3个数据,表示顶点到另外一个顶点的边长度是多少 # @return int # class Solution: def findShortestPath(self , n , m , graph ): def dijkstra(start, end): passed, nopass = [start], [x for x in range(len(adj)) if x != start] dis = adj[start] while len(nopass): idx = nopass[0] for i in nopass: if dis[i] < dis[idx]: idx = i nopass.remove(idx) passed.append(idx) for i in nopass: if dis[idx] + adj[idx][i] < dis[i]: dis[i] = dis[idx] + adj[idx][i] return dis[end] adj = [[float("inf")]*(n) for _ in range(n)] for i in range(m): adj[graph[i][0]-1][graph[i][1]-1] = min(adj[graph[i][0]-1][graph[i][1]-1], graph[i][2]) return dijkstra(0, n-1)