Results 1 to 4 of 4
  1. #1
    santo is offline Member
    Join Date
    Apr 2014
    Posts
    2
    Rep Power
    0

    Default BFS using shortest path between 2 nodes in adjacent matrix

    how to get shortest path between two nodes in adjacency matrix using with undirected weighted graph using BFS algoritham java program??
    CAN U pLs HELP ME ???

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: BFS using shortest path between 2 nodes in adjacent matrix

    If this is a question about a java programming problem you are having, post the code you have and some questions about the problems you are having.
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    santo is offline Member
    Join Date
    Apr 2014
    Posts
    2
    Rep Power
    0

    Default Re: BFS using shortest path between 2 nodes in adjacent matrix

    import java.util.ArrayList;

    public class BfsData
    {
    // Graph adjacency matrix (unweighted graph)
    static private int[][] graph = { {0,3,0,0,2}, // 0->1 0->3
    {0,0,0,33,0}, // 1->2, 1->3
    {0,0,0,22,0}, // 2->4
    {0,0,0,0,3}, // 3->2, 3->4
    {0,0,0,0,0} // 4->1
    };

    //--------------------------------------------------------------
    public static void main (String[] args)
    {
    ArrayList<Integer> Start = new ArrayList();
    Start.add(0); // The start node
    ArrayList<ArrayList> Queue = new ArrayList();
    Queue.add(Start); // inserted in the initial queue of paths as [[Start]]
    // Use one search at a time (comment the others)
    // ArrayList Path = depth_first(Queue,4); // Depth first search
    ArrayList Path = breadth_first(Queue,4); // Breadth first search
    // ArrayList Path = uni_cost(Queue,4); // Uniform cost search
    System.out.println(Path);
    // System.out.println(path_cost(Path));
    }
    //--------------------------------------------------------------
    // Adds to the queue paths extending the first path in the queue
    public static ArrayList<ArrayList> extend (ArrayList<Integer> Path)
    {
    ArrayList<ArrayList> NewPaths = new ArrayList();
    for (int i=0;i<graph.length;i++)
    if (graph[Path.get(0)][i]>0 && !Path.contains(i))
    {
    ArrayList Path1 = (ArrayList)Path.clone();

    System.out.println(Path1+"=====jjjj====");
    Path1.add(0,i);
    NewPaths.add(Path1);
    System.out.println(NewPaths+"====NewPaths==");
    }
    return NewPaths;
    }
    //--------------------------------------------------------------
    // Appends y to x and returns the result in a new ArrayList z
    public static ArrayList append (ArrayList x, ArrayList y)
    {
    ArrayList z = (ArrayList)x.clone();
    for (int i=0;i<y.size();i++) z.add(y.get(i));
    return z;
    }

    //--------------------------------------------------------------
    // Breadth first search for a path from Start to Goal.
    // The Start node must be in the initial queue of paths as [[Start]]
    public static ArrayList<ArrayList> breadth_first(ArrayList<ArrayList> Queue, int Goal)
    {
    if (Queue.size()==0) return Queue; // path not found
    if ((Integer)Queue.get(0).get(0) == Goal) // if Goal is the first node in the first path
    return Queue.get(0); // return path
    else // replace the first path with all its extensions and put them at the end of the queue
    {
    ArrayList<ArrayList> NewPaths = extend(Queue.get(0));
    Queue.remove(0);
    return breadth_first(append(Queue,NewPaths),Goal);
    }
    }
    //--------------------------------------------------------------
    public static int path_cost (ArrayList<Integer> Path)
    {
    int cost = 0;
    for (int i=0;i<Path.size()-1;i++)
    cost = cost + graph[Path.get(i+1)][Path.get(i)];
    return cost;
    }
    public static void sort(ArrayList<ArrayList> Queue)
    {
    int out, in;
    for(out=Queue.size()-1; out>=1; out--)
    for(in=0; in<out; in++)
    if( path_cost(Queue.get(in)) > path_cost(Queue.get(in+1)) )
    swap(Queue, in, in+1);
    }
    //--------------------------------------------------------------
    private static void swap(ArrayList<ArrayList> a, int one, int two)
    {
    ArrayList<Integer> temp = a.get(one);
    a.set(one,a.get(two));
    a.set(two,temp);
    }

    }



    As Above program, in that place i will directly send the adjacent matrix file through file reader, that file is

    a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad
    a 0 3 0 0 2 1 0 0 0 2 0 0 42 1 0 0 11 0 6 0 0 0 0 43 0 36 0 23 0 24
    b 0 0 0 33 0 25 0 36 0 0 0 3 24 0 2 0 0 47 0 0 8 3 0 17 0 0 0 0 4 20
    c 0 0 0 22 0 12 16 0 34 0 0 7 0 2 0 0 0 0 0 16 0 13 0 0 0 25 0 0 0 10
    d 0 0 0 0 3 4 0 0 0 0 5 12 8 0 0 0 2 12 0 0 3 0 0 24 32 0 0 0 0 0
    e 0 0 0 0 0 0 1 4 0 12 0 20 0 0 0 0 13 0 1 16 0 0 0 0 2 4 5 6 0 0
    f 0 0 0 0 0 0 1 0 2 0 13 8 0 0 1 0 4 0 0 8 0 0 0 12 1 0 0 0 1 0
    g 0 0 0 0 0 0 0 1 12 0 3 5 0 2 0 3 0 0 1 2 0 0 0 5 10 0 1 2 1 0
    h 0 0 0 0 0 0 0 0 3 34 5 0 0 0 0 0 1 12 1 0 0 0 0 0 2 0 3 0 1 0
    i 0 0 0 0 0 0 0 0 0 1 2 0 0 42 0 1 5 34 1 0 0 1 0 0 0 0 0 1 0 0
    j 0 0 0 0 0 0 0 0 0 0 0 1 22 0 11 0 25 41 0 0 0 0 0 0 0 1 0 1 0 4
    k 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 23 0 12 0 2 0 3 0 1 0 0 1 1
    l 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 19 12 0 0 1 0 0 0 0 2 0 4 0 2 0
    m 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 5 1 0 0 0 0 3 0 2 0 0 0 0 0 0
    n 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 23 0 5 32 0 50 0 1 0 3 4
    o 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 4 0 0 2 53 0 2 21 3 0 0 0 1
    p 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 24 0 0 12 38 0 2 0 0
    q 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 24 0 0 24 0 0 12 0 5 0 0 0
    r 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 12 0 57 0 0 2 0
    s 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 24 0 1 0 5 12 0
    t 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 0 24 1 6 0 0 1
    u 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 0 1 0 0
    v 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 22 1 1 4 0
    w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 38 0 0 5 7 0
    x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 5 0 1
    y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 21 0 1
    z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1
    aa 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 42 0 0
    ab 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0
    ac 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5
    ad 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0



    "" static private int[][] graph = { {0,3,0,0,2}, // 0->1 0->3
    {0,0,0,33,0}, // 1->2, 1->3
    {0,0,0,22,0}, // 2->4
    {0,0,0,0,3}, // 3->2, 3->4
    {0,0,0,0,0} // 4->1
    };"" ....in that ""---"" i will set that above matrix file ?how to set that file??

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: BFS using shortest path between 2 nodes in adjacent matrix

    Sorry, I forgot to say that you should wrap your code with code tags:
    [code]
    YOUR CODE HERE
    [/code]
    to get highlighting and preserve formatting.
    If you don't understand my response, don't ignore it, ask a question.

Similar Threads

  1. MST (Kruskal) & Shortest Path (Djikstra)
    By Aliendox in forum Advanced Java
    Replies: 2
    Last Post: 11-25-2013, 12:51 PM
  2. Shortest path
    By csharp100 in forum New To Java
    Replies: 5
    Last Post: 03-23-2012, 10:25 AM
  3. Replies: 0
    Last Post: 03-20-2011, 01:17 AM
  4. Replies: 1
    Last Post: 03-21-2008, 03:14 PM
  5. adjacent repeating letters
    By artemis_r2 in forum New To Java
    Replies: 1
    Last Post: 11-17-2007, 04:48 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •