Graphs and Dijktra's algorithm..

ok...

in DA (dijktras alg.) ..

you have nodes and edges..

now can edges be represented by different pointers

within the node class that point to other nodes,

and just each have each pointer have a weight:int?

and once i get that hard-coded, how to i go about traversing

the graph radomly?

Justin

please help?

Hi,

did you check this?

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Bu.

Originally posted by Burkhard Hassel:
Hi,

did you check this?

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Bu.

Thankx Bu,

You have gave a good link....

You have gave a good link....

Normally I wouldn't post such links, as somebody could think, I would fool him/her.
But in this case I just looked and saw some pseudo code, that might be helpful.

Yours,
Bu.

ok ok, im just trying to get every possible path,

but im running to problems...

here is my code;

public class Graph{
 
String thePath;
Node A,B,C,D,E,F;
Node [] a = new Node[6];
 
public class Node{
 
Node one,two,three;
String name;
String currPath;
 
public Node()
{
  name = "";
  one = two = three = null;
  currPath = "";
}
 
}
 
Node Start, End;
 
public Graph()
{
 
int i = 0;
 
A = new Node();
a[i] = A;
        i++;
 
        B = new Node();
a[i] = B;
        i++;
 
C = new Node();
a[i] = C;
        i++;
 
        D = new Node();
a[i] = D;
        i++;
 
        E = new Node();
a[i] = E;
        i++;
 
        F = new Node();
a[i] = F;
        i++;
 
A.name = "A";
B.name = "B";
C.name = "C";
D.name = "D";
E.name = "E";
F.name = "F";
 
A.one = C;
        A.two = B;
        A.three = D;
 
        B.one = C;
 
        C.one = F;
 
        D.one = B;
        D.two = C;
D.three = E;
 
       
        E.one = C;
        E.two = F;
 
Start = new Node();
        End = new Node();
        Start = A;
        End = F;
    }
 
public void findAllPaths()
{
  findAllPathsHelper(Start);
}
 
     
public void findAllPathsHelper(Node a)
     {  System.out.print(a.name);

if(a.name.equals("F")){
System.out.print("\n\n");
        findAllPathsHelper(Start);}

if(a.one != null)
{
        Node Curr = a.one;
        a.one = null;

findAllPathsHelper(Curr);
        }
 
else if( a.two != null)
        {
          Node Curr = a.two;
           a.two = null;
           findAllPathsHelper(Curr);
        }
 
else if( a.three != null)
        {
           Node Curr = a.three;
           a.three = null;
           findAllPathsHelper(Curr);
        }

if(isNull(a) && a.name != "A")
{ 
System.out.print("\n\n");
        findAllPathsHelper(Start);
}
 
if(allNodesNull())
        { 
//printPaths();
        } 
        
     } 
 
public boolean isNull(Node a)
  {
      if(a.one == null && a.two == null && a.three == null)
      return true;
      else
      return false;
  }
 
public static void main(String []args)
  {
       Graph a = new Graph();
       a.findAllPaths();
  }
 
public boolean allNodesNull()
   {  
 
boolean allNull = true;
 
        for( int i = 0; i<a.length;i++)
        {
           if(!isNull(a[i])) 
            {
              allNull = false;
      break;
            }
}
  return allNull;
   }
 
}

im trying to keep traversing from a until every node is Null,
meaning that all of its paths have been traveled...

but say i want to go ACF

ok, now A C and F's one pointer are set null.

but if wanted to go ABCF, i couldnt

cause C's one pointer is null...

how do i go about fixing this, or is there a better way?

Thanks A lot,

Justin

Well a better approach might be implementing the algorithm as presented in the link submitted by 'Bu' (oh, and Bu - that really is a quite good reference to Dijkstra's Algorithm).

Your approach seems to be missing the weight of the vertices (or maybe i'm missing something).

As to traversing, the link also supplies the pseudocode for iterating and obtaining the (or one of the) shortest path.

One way that seems to help in understanding (and hence implementation) is to do this on paper and note how you would sovle this by hand (or if you are required to implement DA, then how you would solve this by hand using the DA.

I re-did the application, with 2D array...

and did dijkstra's with a triple nested for loop...

worked quite well actually...

Justin

Congratulations!