Tuesday, February 10, 2015

Path Finder in a java programe



PathFinder.java

public class PathFinder
{
private ST  prev = new ST();
 private ST dist = new ST();
              public PathFinder(Graph G, String s
           {
                   Queue q = new Queue();
        q.enqueue(s);
        dist.put(s, 0);
       
        while (!q.isEmpty())
{
            String v = q.dequeue();
            for (String w : G.adjacentTo(v))
{
                if (!dist.contains(w))
{
                    q.enqueue(w);
                    dist.put(w, 1 + dist.get(v));
                    prev.put(w, v);
                }
            }
        }
    }

    public boolean isReachable(String v)
{
        return dist.contains(v);
    }

    public int distanceTo(String v)
{
        if (!dist.contains(v)) return Integer.max_value;
        return dist.get(v);
    }

    public Iterable pathTo(String v)
{
        Stack path = new Stack();
        while (v != null && dist.contains(v))
{
            path.push(v);
            v = prev.get(v);
     }
        return path;
    }

                     public static void main(String[] args)
              {
        String filename  = args[0];
        String delimiter = args[1];
        In in = new In(filename);
        Graph G = GraphGenerator.read(in, delimiter);
        String s = args[2];
        PathFinder pf = new PathFinder(G, s);
        while (!StdIn.isEmpty())
 {
            String t = StdIn.readLine();
            for (String v : pf.pathTo(t))
{
                StdOut.println("   " + v);
        }
            StdOut.println("distance " + pf.distanceTo(t));
        }
    }
            }

No comments:

Post a Comment