大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 最短路 bellman-ford算法

最短路 bellman-ford算法

关键词:bellman-ford最短路 算法  阅读(612) 赞(18)

[摘要]本文是对最短路 bellman-ford算法的讲解,对学习Java编程技术有所帮助,与大家分享。

效果描画 给定一个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,保证从恣意顶点都能抵达其他一切顶点。

 package job525;
 
 import java.util.Scanner;
 
 class Eage{
     int from;
     int to;
     int cost;
 
     public int getFrom() {
         return from;
     }
     public void setFrom(int from) {
         this.from = from;
     }
     public int getTo() {
         return to;
     }
     public void setTo(int to) {
         this.to = to;
     }
     public int getCost() {
         return cost;
     }
     public void setCost(int cost) {
         this.cost = cost;
     }
     public Eage(int from,int to,int cost)
     {
         this.from = from;
         this.to = to;
         this.cost = cost;
     }
 }
 
 public class 最短路bellman_ford {
     
     static int m,n,inf=100000;//n:n个顶点;m:m条边
     static int []d=new int[20000];
     static Eage []eg=new Eage[200000];
     
     public static void main(String[] args) {
         Scanner sc=new Scanner(System.in);
         n=sc.nextInt();m=sc.nextInt();
         int i=0;
         while(i<m)
         {
             int u, v, l;
             u=sc.nextInt();
             v=sc.nextInt();
             l=sc.nextInt();
             eg[i++]=new Eage(u,v,l);
         }
         //测试存储---------------------------------------------------------------------------------
         /*
         for(i=0;i<m;i++)
         {
             System.out.println("("+eg[i].getFrom()+","+eg[i].getTo()+"):"+eg[i].getCost());
         }
         */
         //测试终了----------------------------------------------------------------------------------
         bellman_ford();
         for(i=2;i<=n;i++)
         {
             System.out.println(d[i]);
         }
     }
     public static void bellman_ford()
     {
         init();
         while(true)
         {
             boolean flag=false;
             for(int i=0;i<m;i++)
             {
                 Eage e=eg[i];
                 if(d[e.getFrom()]!=inf&&d[e.getTo()]>d[e.getFrom()]+e.getCost())
                 {
                     d[e.getTo()]=d[e.getFrom()]+e.getCost();
                     //System.out.println("("+eg[i].getFrom()+","+eg[i].getTo()+"):"+eg[i].getCost()+d[e.getTo()]);//测试
                     flag=true;
                 }
             }
             if(!flag)
                 break;
         }
     }
     public static void init()
     {
         for(int i=1;i<=n;i++)
             d[i]=inf;
         d[1]=0;
     }
 }


相关评论