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)
        return mDistances[dest];            

    public boolean hasNegativeCycle(int src, int 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[mSource] = 0;
        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;



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("not possible");



Sample Input

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

not possible


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 )

Connecting to %s

%d bloggers like this: