首页 > 代码库 > 最短路 spfa算法

最短路 spfa算法

2024-07-06 05:25:02   226人阅读

问题描述 给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。 输入格式 第一行两个整数n, m。 接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。 输出格式 共n-1行，第i行表示1号点到i+1号点的最短路。 样例输入 3 3 1 2 -1 2 3 -1 3 1 2 样例输出 -1 -2 数据规模与约定 对于10%的数据，n = 2，m = 2。 对于30%的数据，n <= 5，m <= 10。 对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

 1 package job525;
 2 
 3 import java.util.LinkedList;
 4 import java.util.Queue;
 5 import java.util.Scanner;
 6 
 7 class Eages{
 8     int to;
 9     int cost;
10     public int getTo() {
11         return to;
12     }
13     public void setTo(int to) {
14         this.to = to;
15     }
16     public int getCost() {
17         return cost;
18     }
19     public void setCost(int cost) {
20         this.cost = cost;
21     }
22     public Eages(int to,int cost){
23         this.to = to;
24         this.cost = cost;
25     }
26 }
27 public class 最短路spfa {
28 
29     static int N=20001,M=200001,inf=100000;//最大的顶点数和边数
30     static int m,n;//n：n个顶点；m：m条边
31     static int []d=new int[N];//最短距离
32     static boolean visit[]=new boolean[N];//是否遍历过
33     static Eages[][] eage;//n个顶点所对应的边,模拟Vector
34     static int[]num=new int[N];//每个顶点的边的条数
35     
36     public static void main(String[] args) {
37         Scanner sc=new Scanner(System.in);
38         n=sc.nextInt();m=sc.nextInt();
39         int i=0;
40         eage=new Eages[n+1][m];
41         while(i++<m)
42         {
43             int u, v, l;
44             u=sc.nextInt();
45             v=sc.nextInt();
46             l=sc.nextInt();
47             eage[u][num[u]++]=new Eages(v,l);
48         }
49         spfa();
50         for(i=2;i<=n;i++)
51         {
52             System.out.println(d[i]);
53         }
54     }
55     public static void spfa()
56     {
57         init();
58         Queue<Integer> q=new LinkedList<Integer>();
59         q.offer(1);
60         visit[1]=true;
61         while(!q.isEmpty())
62         {
63             int x=q.poll();
64             visit[x]=false;
65             for(int i=0;i<num[x];i++)
66             {
67                 if(d[x]!=inf&&d[eage[x][i].getTo()]>eage[x][i].getCost()+d[x])
68                 {
69                     d[eage[x][i].getTo()]=eage[x][i].getCost()+d[x];
70                     if(!visit[eage[x][i].getTo()])
71                     {
72                         q.offer(eage[x][i].getTo());
73                         visit[eage[x][i].getTo()]=true;
74                     }
75                 }
76             }
77         }
78     }
79     public static void init()
80     {
81         for(int i=1;i<=n;i++)
82             d[i]=inf;
83         d[1]=0;
84     }
85 }
View Code

 


联系
我们