在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径，返回 1 到 n 的最短路径值。如果 1 无法到 n ，输出 -1
图中可能有重边，无自环。
数据范围：
， 
， %20%5Cle%201000%20)
[编程题]单源最短路
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;
}
} 
死活想不明白哪里写的有问题，求大神解
编辑于 2024-03-11 21:59:28
回复(0)
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
}
}
发表于 2022-08-04 12:48:42
回复(0)
无脑迪杰斯特拉算法
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];
}
}
发表于 2021-12-12 09:46:34
回复(1)
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];
}
}
发表于 2021-12-10 16:49:20
回复(0)
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;
}
}
}
}
发表于 2021-10-02 10:33:10
回复(0)
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];
}
发表于 2021-08-25 15:14:47
回复(0)
动态规划：
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];
}
发表于 2021-08-02 16:49:08
回复(3)
运行时间：18ms
超过100.00%用Java提交的代码
超过100.00%用Java提交的代码
占用内存：11476KB
超过81.37%用Java提交的代码
//动态规划
public int findShortestPath (int n, int m, int[][] graph) {
int[] dp = new int[n+1];
dp[1] = 0;
for(int i=2; i<n+1; i++){
int min = Integer.MAX_VALUE;
for(int j=0; j<m; j++){
if(graph[j][1] == i && dp[graph[j][0]] != -1){
min = Math.min(min,graph[j][2]+dp[graph[j][0]]);
}
}
dp[i] = min == Integer.MAX_VALUE? -1:min;
}
return dp[n];
}
int[] dp = new int[n+1];
dp[1] = 0;
for(int i=2; i<n+1; i++){
int min = Integer.MAX_VALUE;
for(int j=0; j<m; j++){
if(graph[j][1] == i && dp[graph[j][0]] != -1){
min = Math.min(min,graph[j][2]+dp[graph[j][0]]);
}
}
dp[i] = min == Integer.MAX_VALUE? -1:min;
}
return dp[n];
}
发表于 2021-02-22 13:50:51
回复(6)
问题信息
通过挑战的用户
查看代码-
2023-02-20 10:33:02
-
2023-01-07 20:56:03
-
2023-01-04 12:37:51 -
2022-10-16 19:23:56
-
2022-10-15 17:50:21
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
