uva: 558 – Wormholes ( Bellman-Ford )

558 – Wormholes  ( Bellman-Ford )

 

Problem analysis:

  • The scientist wants to reach a cycle of wormholes somewhere in the universe that causes her to end up in the past
  • Write a program to find out whether such a cycle exists

Solution analysis:

  • Find if there is any negative cycle in the path, then there will be path to end up in the past
  • Using  Bellman-Ford algorithm it can be solved, if there is any negative cycle then it is “possible” ,  otherwise “not possible”

 

Java solution:

          

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

class Edge
{
    public int u;
    public int v;
    public int w;
    public Edge(int source, int target, int weight)
    {
        this.u = source;
        this.v= target;
        this.w =weight;
    }
}

class BellmanFord
{
    public final int INFINITY=Integer.MAX_VALUE;
    private int mNumOfVertexes, mSource, mDestination;
    private int mDistances[];
    private    ArrayList mEdges;
    private boolean mHasNegativeCycle;
    
        
    public BellmanFord(int numofvertexes, ArrayList edges)
    {
        this.mNumOfVertexes = numofvertexes;        
        this.mEdges = edges;
    }
    
    public int costSourceToDest(int src, int dest)
    {
        bfAlgorithm(src,dest);
                
        return mDistances[dest];            
    }

    public boolean hasNegativeCycle(int src, int dest)
    {
                
        bfAlgorithm(src,dest);
        
        return mHasNegativeCycle;
    }

    private void bfAlgorithm(int src, int dest)
    {
        
        mSource = src;
        mDestination = dest;
        
        int numvrtx = mNumOfVertexes;
        
        mDistances = new int[numvrtx+1];        
        for(int i=0;i<=numvrtx;i++)
            mDistances[i]=INFINITY;

        mDistances[mSource] = 0;
        mHasNegativeCycle=false;
        for(int level=1; level<=numvrtx; level++)
        {
            for(Edge edg:mEdges)
            {
                if(mDistances[edg.u]+ edg.w < mDistances[edg.v])
                {
                    mDistances[edg.v] = mDistances[edg.u]+ edg.w;

                    if(level==numvrtx)
                        mHasNegativeCycle=true;
                }
            }
        }        
    }

}

class Main_Wormholes_558_BellmanFord {    

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc= new Scanner(br);

        int testCase = sc.nextInt();
        int numofvertexes, numofedges, source, target, weight;
        
        ArrayList<Edge> edges;        
        BellmanFord blmnfrd;
        
        for(int tc=1; tc<=testCase; tc++)
        {
            numofvertexes = sc.nextInt();
            numofedges = sc.nextInt();

            edges = new ArrayList<Edge>();                

            for(int i=1;i<=numofedges;i++)
            {
                source = sc.nextInt();
                target = sc.nextInt();
                weight= sc.nextInt();
                edges.add(new Edge(source,target,weight));            
            }
            
            blmnfrd = new BellmanFord(numofvertexes, edges);
            
            if(blmnfrd.hasNegativeCycle(0, numofvertexes-1))
                System.out.println("possible");
            else
                System.out.println("not possible");

        }
        System.out.flush();
        sc.close();
        sc=null;
    }

}

Sample Input

2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60

Sample Output

possible
not possible

Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: