[Pyrokitsune]

Alright, so first off this is a class project for my data structures class. The project is to build a visualization of Dijkstra's algorithm, showing how it works and having changable weights assigned to the paths(so that we can't just set a graph and set the path it has to compare the paths each time).

Currently I have a GUI that takes in the paths and assigns them to a multi-tiered array(up to [200]x[20]) from the user, or alternatively(realistically) taking the array from a file input. The program then saves the weights in the element that corresponds to the nodes the path attaches to. I should note at this point the project doesn't need to be optimal, a multidimensional array seemed easiest to implement with the time given. The graphical representation basics are done as well using simple drawn lines and color changes to represent the paths, the nodes, reached paths, and optimal path.

On to the problem however, I understand how the algorithm works(basically) but I'm having trouble thinking of a way to implement it. I can't seem to think of a way to save an unknown number of paths or compare them step by step to the other possible paths. I'm looking for pointers, a shove in the right direction, or examples of code that is already implemented doing what I am looking for even if it's not doing Dijkstra's. If I'm way out in the wrong direction telling me a better place to be looking would be nice as well.

Thanks in advance for any advice given.

This post has been edited by Pyrokitsune: 20 May 2010 - 01:19 AM

[macosxnerd101]

Even though the Java Collections Framework doesn't come with a generic Graph class doesn't mean you can't implement your own. I've written a tutorialn on this, which I think you will find helpful. Since you will be using a Graph instead of a 2D array, the Vertices will point to other Vertices through Connectors/Edges. I would assign Vertex-to-Vertex distances through the connectors, and weight according to the shortest path to a Vertex.

Does this help some?

[Pyrokitsune]

macosxnerd101, on 19 May 2010 - 01:26 PM, said:

Does this help some?

Thanks that helped a lot and ended up getting the entire algorithm to work. That being said it's having issues trying to repaint the lines. Could someone look this over and see if they can tell me any glaring problems. I'm sure the problem is just being approached wrong but I can't see where it's happening.

   import javax.swing.*;
   import java.awt.event.*;
   import java.text.*;
   import java.awt.*;
   import javax.swing.JOptionPane;
   import java.io.*;
   import java.util.List;
    
	 
    public class GUIArray 
   {
   
   
   	//main method
       public static void main (String [] args)
      {
         GUIArray x = new GUIArray();
         //GUIArray();//creates two graphs-two runs, ONE input!
      }
   
   //global variables
   //array to hold path weights
      static int[][] paths = new int[20][20];
   //GUI declareds
      static JFrame frame = new JFrame();
   //Constructor for drawing class
   //MyDrawing drawing = new MyDrawing();
   //panels
      static JPanel superCompletePanel = new JPanel();
      static JPanel completePanel = new JPanel();
      static JPanel oneOne = new JPanel();
      static JPanel oneTwo = new JPanel();
      static JPanel oneThree = new JPanel();
      static JPanel oneFour = new JPanel();
      static JPanel oneFive = new JPanel();
      static JPanel twoOne = new JPanel();
      static JPanel twoTwo = new JPanel();
      static JPanel twoThree = new JPanel();
      static JPanel twoFour = new JPanel();
      static JPanel twoFive = new JPanel();
      static JPanel threeOne = new JPanel();
      static JPanel threeTwo = new JPanel();
      static JPanel threeThree = new JPanel();
      static JPanel threeFour = new JPanel();
      static JPanel threeFive = new JPanel();
      static JPanel fourOne = new JPanel();
      static JPanel fourTwo = new JPanel();
      static JPanel fourThree = new JPanel();
      static JPanel fourFour = new JPanel();
      static JPanel fourFive = new JPanel();
      static JPanel fiveOne = new JPanel();
      static JPanel fiveTwo = new JPanel();
      static JPanel fiveThree = new JPanel();
      static JPanel fiveFour = new JPanel();
      static JPanel fiveFive = new JPanel();
      static JPanel leftLeft = new JPanel();
      static JPanel leftRight = new JPanel();
      static JPanel middle = new JPanel();
      static JPanel rightLeft = new JPanel();
      static JPanel rightRight = new JPanel();
      static JPanel visual = new JPanel();
      static JPanel buttonPanel= new JPanel();
   //text fields
      static JTextField  AB = new JTextField("0", 3);
      static JTextField  AC = new JTextField("0", 3);
      static JTextField  BC = new JTextField("0", 3);
      static JTextField  CD = new JTextField("0", 3);
      static JTextField  CE = new JTextField("0", 3);
      static JTextField  BF = new JTextField("0", 3);
      static JTextField  EH = new JTextField("0", 3);
      static JTextField  DG = new JTextField("0", 3);
      static JTextField  GH = new JTextField("0", 3);
      static JTextField  FH = new JTextField("0", 3);
      static JTextField  FJ = new JTextField("0", 3);
      static JTextField  HJ = new JTextField("0", 3);
      static JTextField  HK = new JTextField("0", 3);
      static JTextField  HI = new JTextField("0", 3);
      static JTextField  IL = new JTextField("0", 3);
      static JTextField  KL = new JTextField("0", 3);
      static JTextField  JK = new JTextField("0", 3);
      static JTextField  JM = new JTextField("0", 3);
      static JTextField  LM = new JTextField("0", 3);
      static JTextField  GI = new JTextField("0", 3);
   
      static JButton accept = new JButton("Accept");
   
   	//labels
      static JLabel AB1 = new JLabel("Path A:B");
      static JLabel AC1 = new JLabel("Path A:C");
      static JLabel BC1 = new JLabel("Path B:C");
      static JLabel CD1 = new JLabel("Path C:D");
      static JLabel CE1 = new JLabel("Path C:E");
      static JLabel BF1 = new JLabel("Path B:F");
      static JLabel EH1 = new JLabel("Path E:H");
      static JLabel DG1 = new JLabel("Path D:G");
      static JLabel GH1 = new JLabel("Path G:H");
      static JLabel FH1 = new JLabel("Path F:H");
      static JLabel FJ1 = new JLabel("Path F:J");
      static JLabel HJ1 = new JLabel("Path H:J");
      static JLabel HK1 = new JLabel("Path H:K");
      static JLabel HI1 = new JLabel("Path H:I");
      static JLabel IL1 = new JLabel("Path I:L");
      static JLabel KL1 = new JLabel("Path K:L");
      static JLabel JK1 = new JLabel("Path J:K");
      static JLabel JM1 = new JLabel("Path J:M");
      static JLabel LM1 = new JLabel("Path L:M");
      static JLabel GI1 = new JLabel("Path G:I");
   
   	//constructor
       public GUIArray(){GuiBuild();}//}
       public void GUIArray(){GuiBuild();}// using a call make gui not appear!
      //make panels
       private void GuiBuild(){
         buildLeftLeft();
         buildLeftRight();
         buildMiddle();
         buildRightLeft();
         buildRightRight();
         buildVisual();
      
      //make frame & add panels
         superCompletePanel.setLayout(new GridLayout(2,1));
         completePanel.setLayout(new GridLayout(1, 5));
      
         superCompletePanel.add(visual);
         superCompletePanel.add(completePanel);
      
         completePanel.add(leftLeft);
         completePanel.add(leftRight);
         completePanel.add(middle);
         completePanel.add(rightLeft);
         completePanel.add(rightRight);
            
         frame.add(superCompletePanel);
         frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
         frame.pack();
         frame.setLocationRelativeTo(null);
         frame.setVisible(true);
      }
   
       //build our visual
       private void buildVisual()
      {
         visual.add(new GraphicCanvas(Color.yellow), BorderLayout.CENTER);
         visual.show();// causes:
      	//Note: C:\Users\Ed\misc\Desktop\G3pm\GUIArray.java uses or overrides a deprecated API.
         //Note: Recompile with -Xlint:deprecation for details.
      }
       private void buildVisual1()
      {
         visual.add(new GraphicCanvas(Color.red), BorderLayout.SOUTH);
         visual.show();// causes:
      	//Note: C:\Users\Ed\misc\Desktop\G3pm\GUIArray.java uses or overrides a deprecated API.
         //Note: Recompile with -Xlint:deprecation for details.
      }
   	//build panels
   	//left left
       private static void buildLeftLeft()
      {
         leftLeft.setLayout(new GridLayout(5, 1));
         oneOne.setLayout(new GridLayout(2, 1));
         oneOne.add(AB);
         oneOne.add(AB1);
         leftLeft.add(oneOne);
         twoOne.setLayout(new GridLayout(2, 1));
         twoOne.add(AC);
         twoOne.add(AC1);
         leftLeft.add(twoOne);
         threeOne.setLayout(new GridLayout(2, 1));
         threeOne.add(BC);
         threeOne.add(BC1);
         leftLeft.add(threeOne);
         fourOne.setLayout(new GridLayout(2, 1));
         fourOne.add(CD);
         fourOne.add(CD1);
         leftLeft.add(fourOne);
      }
   
   		//build left right
       private static void buildLeftRight()
      {
         leftRight.setLayout(new GridLayout(5, 1));
         oneTwo.setLayout(new GridLayout(2, 1));
         oneTwo.add(CE);
         oneTwo.add(CE1);
         leftRight.add(oneTwo);
         twoTwo.setLayout(new GridLayout(2, 1));
         twoTwo.add(BF);
         twoTwo.add(BF1);
         leftRight.add(twoTwo);
         threeTwo.setLayout(new GridLayout(2, 1));
         threeTwo.add(EH);
         threeTwo.add(EH1);
         leftRight.add(threeTwo);
         fourTwo.setLayout(new GridLayout(2, 1));
         fourTwo.add(DG);
         fourTwo.add(DG1);
         leftRight.add(fourTwo);
      }
   
       private static void buildMiddle()//static
      {
         middle.setLayout(new GridLayout(5, 1));
         oneThree.setLayout(new GridLayout(2, 1));
         oneThree.add(GH);
         oneThree.add(GH1);
         middle.add(oneThree);
         twoThree.setLayout(new GridLayout(2, 1));
         twoThree.add(FH);
         twoThree.add(FH1);
         middle.add(twoThree);
         threeThree.setLayout(new GridLayout(2, 1));
         threeThree.add(FJ);
         threeThree.add(FJ1);
         middle.add(threeThree);
         fourThree.setLayout(new GridLayout(2, 1));
         fourThree.add(HJ);
         fourThree.add(HJ1);
         middle.add(fourThree);
         accept.addActionListener(new ButtonListener());
         buttonPanel.add(accept);
         middle.add(buttonPanel);
      }
   
       public static void buildRightLeft()
      {
         rightLeft.setLayout(new GridLayout(5, 1));
         oneFour.setLayout(new GridLayout(2, 1));
         oneFour.add(HK);
         oneFour.add(HK1);
         rightLeft.add(oneFour);
         twoFour.setLayout(new GridLayout(2, 1));
         twoFour.add(HI);
         twoFour.add(HI1);
         rightLeft.add(twoFour);
         threeFour.setLayout(new GridLayout(2, 1));
         threeFour.add(IL);
         threeFour.add(IL1);
         rightLeft.add(threeFour);
         fourFour.setLayout(new GridLayout(2, 1));
         fourFour.add(KL);
         fourFour.add(KL1);
         rightLeft.add(fourFour);
      }
   
       public static void buildRightRight()
      {
         rightRight.setLayout(new GridLayout(5, 1));
         oneFive.setLayout(new GridLayout(2, 1));
         oneFive.add(JK);
         oneFive.add(JK1);
         rightRight.add(oneFive);
         twoFive.setLayout(new GridLayout(2, 1));
         twoFive.add(JM);
         twoFive.add(JM1);
         rightRight.add(twoFive);
         threeFive.setLayout(new GridLayout(2, 1));
         threeFive.add(LM);
         threeFive.add(LM1);
         rightRight.add(threeFive);
         fourFive.setLayout(new GridLayout(2, 1));
         fourFive.add(GI);
         fourFive.add(GI1);
         rightRight.add(fourFive);
      }
   
   
   
   // a canvas which renders a graph to the screen
       class GraphicCanvas extends Canvas 
      {
      
          public GraphicCanvas(Color faceColor) {
            setForeground(faceColor);
         }
          public void GraphicCanvas(Color faceColor) {
            setForeground(faceColor);
         }
          public Dimension getPreferredSize() {
            return new Dimension(600,300);// width, height
         }
      }  
      /*
      * Paint when the AWT tells us to...
      */
       public void paint(Graphics g) {
         // Dynamically calculate size information
         // (the canvas may have been resized externally...)
         Dimension size = getSize();
         //add variables for nodes drawn as a circle in box
         int d = Math.min(size.width, size.height); // diameter
         int ed = d/20; // eye diameter
         int x = 600;
         int y = 300;
         int c = (d/20)/2; // node center
         
         // draw nodes
         //g.fillOval(x, y, d, d);
         g.setColor(Color.black);
         g.fillOval(10, 100, ed, ed);//a
         g.fillOval(60, 75, ed, ed);//b
         g.fillOval(60, 130, ed, ed);//c
         g.fillOval(150, 40, ed, ed);//f
         g.fillOval(150, 130, ed, ed);//e
         g.fillOval(150, 175, ed, ed);//d	
         g.fillOval(200, 175, ed, ed);//g	
         g.fillOval(200, 100, ed, ed);//h
         g.fillOval(300, 40, ed, ed);//j
         g.fillOval(300, 160, ed, ed);//i
         g.fillOval(360, 100, ed, ed);//k
         g.fillOval(450, 160, ed, ed);//l
         g.fillOval(550, 50, ed, ed);//m
         
         // draw node labels
         g.drawString("A", 10, 100);
         g.drawString("B", 60, 75);
         g.drawString("C", 60, 130+25);
         g.drawString("D", 150, 175+25);
         g.drawString("E", 150, 130);
         g.drawString("F", 150, 40);
         g.drawString("G", 200, 175+25);
         g.drawString("H", 200, 100);
         g.drawString("I", 300, 160);
         g.drawString("J", 300, 40);
         g.drawString("K", 360, 100);
         g.drawString("L", 450, 160);
         g.drawString("M", 550, 50);
         
         // draw lines add half of x and y
         g.setColor(Color.gray);
         
         g.drawLine(10+c, 100+c, 60+c, 75+c); //ab
         g.drawLine(10+c, 100+c, 60+c, 130+c); //ac
         g.drawLine(60+c, 75+c, 150+c, 40+c); //bf
         g.drawLine(60+c, 130+c, 150+c, 130+c); //ce
         g.drawLine(60+c, 130+c, 150+c, 175+c); //cd
         g.drawLine(150+c, 175+c, 200+c, 175+c); //dg
         g.drawLine(150+c, 130+c, 200+c, 100+c); //eh
         g.drawLine(200+c, 175+c, 200+c, 100+c); //gh
         g.drawLine(200+c, 175+c, 300+c, 160+c); //gi
         g.drawLine(150+c, 40+c, 200+c, 100+c); //fh
         g.drawLine(150+c, 40+c, 300+c, 40+c); //fj
         g.drawLine(200+c, 100+c, 300+c, 160+c); //hi
         g.drawLine(200+c, 100+c, 360+c, 100+c); //hk
         g.drawLine(200+c, 100+c, 300+c, 40+c); //hj
         g.drawLine(300+c, 40+c, 550+c, 50+c); //jm
         g.drawLine(300+c, 160+c, 450+c, 160+c); //il
         g.drawLine(450+c, 160+c, 550+c, 50+c); //lm
         g.drawLine(60+c, 75+c, 60+c, 130+c); //bc
         g.drawLine(300+c, 40+c, 360+c, 100+c); //jk
         g.drawLine(360+c, 100+c, 450+c, 160+c); //kl
      }
      
      
       public class ButtonListener implements ActionListener
      {
          public void actionPerformed(ActionEvent e)// no static--overiding method is static
         {  
            try
            {
               String str = "0";
               int distance = 0;
               
               //place in alphabet -1 = array p[lacement
               str = AB.getText().trim();
               paths[0][1] = Integer.parseInt(str);
               
               str = AC.getText().trim();
               paths[0][2] = Integer.parseInt(str);
               
               str = BC.getText().trim();
               paths[1][2] = Integer.parseInt(str);
               
               str = CD.getText().trim();
               paths[2][3] = Integer.parseInt(str);
               
               str = CE.getText().trim();
               paths[2][4] = Integer.parseInt(str);
               
               str = BF.getText().trim();
               paths[1][5] = Integer.parseInt(str);
               
               str = EH.getText().trim();
               paths[4][7] = Integer.parseInt(str);
               
               str = DG.getText().trim();
               paths[3][6] = Integer.parseInt(str);
               
               str = GH.getText().trim();
               paths[6][7] = Integer.parseInt(str);
               
               str = FH.getText().trim();
               paths[5][7] = Integer.parseInt(str);
               
               str = FJ.getText().trim();
               paths[5][9] = Integer.parseInt(str);
               
               str = HJ.getText().trim();
               paths[7][9] = Integer.parseInt(str);
               
               str = HK.getText().trim();
               paths[7][10] = Integer.parseInt(str);
               
               str = HI.getText().trim();
               paths[7][8] = Integer.parseInt(str);
               
               str = IL.getText().trim();
               paths[8][11] = Integer.parseInt(str);
               
               str = KL.getText().trim();
               paths[10][11] = Integer.parseInt(str);
               
               str = JK.getText().trim();
               paths[9][10] = Integer.parseInt(str);
               
               str = JM.getText().trim();
               paths[9][12] = Integer.parseInt(str);
               
               str = LM.getText().trim();
               paths[11][12] = Integer.parseInt(str);
               
               str = GI.getText().trim();
               paths[6][8] = Integer.parseInt(str);
               
               
               // declare nodes in graph
               Vertex a = new Vertex("A");
               Vertex b = new Vertex("B");
               Vertex c = new Vertex("C");
               Vertex d = new Vertex("D");
               Vertex e = new Vertex("E");
               Vertex f = new Vertex("F");
               Vertex g = new Vertex("G");
               Vertex h = new Vertex("H");
               Vertex i = new Vertex("I");
               Vertex j = new Vertex("J");
               Vertex k = new Vertex("K");
               Vertex l = new Vertex("L");
               Vertex m = new Vertex("M");
               
               // declare adjacent edges to node, and weight (target node, weight)
               a.adjacencies = new Edge[]{ new Edge(b,  GUIArray.paths[0][1]),
                                      new Edge(c,  GUIArray.paths[0][2]) };
               b.adjacencies = new Edge[]{ new Edge(c,  GUIArray.paths[1][2]),
                                                          new Edge(f,  GUIArray.paths[1][5]) };
               c.adjacencies = new Edge[]{ new Edge(e,  GUIArray.paths[2][4]),	 
                        				 new Edge(d,  GUIArray.paths[2][3]) };
               d.adjacencies = new Edge[]{ new Edge(g,  GUIArray.paths[3][6]) };
               e.adjacencies = new Edge[]{ new Edge(h,  GUIArray.paths[4][7]) };
               f.adjacencies = new Edge[]{ new Edge(h,  GUIArray.paths[5][7]),
                                     new Edge(j,  GUIArray.paths[5][9]) };
               g.adjacencies = new Edge[]{ new Edge(h,  GUIArray.paths[6][7]),
                                     new Edge(i,  GUIArray.paths[6][8]) };
               h.adjacencies = new Edge[]{ new Edge(i,  GUIArray.paths[7][8]),
                        				 new Edge(k,  GUIArray.paths[7][10]),
                        				 new Edge(j,  GUIArray.paths[7][9]) };
               i.adjacencies = new Edge[]{ new Edge(l,  GUIArray.paths[8][11]) };
               j.adjacencies = new Edge[]{ new Edge(k,  GUIArray.paths[9][10]),
                        				 new Edge(m,  GUIArray.paths[9][12]) };
               k.adjacencies = new Edge[]{ new Edge(l,  GUIArray.paths[10][11]) };
               l.adjacencies = new Edge[]{ new Edge(m,  GUIArray.paths[11][12]) };
               m.adjacencies = new Edge[]{ new Edge(j,  GUIArray.paths[9][12]),
                        				 new Edge(l,  GUIArray.paths[11][12]) };
               //Color.black
               repaint();
               // pass target node/nodes into vertex array
               Vertex[] vertices = {m };
               
               // starting node, compute shortest paths to target node/nodes
               Dijkstra.computePaths(a);
               
               // Loop to print out paths
               for (Vertex v:vertices)
               {
                  System.out.println("Distance to " + v + ": " + v.minDistance);
                  List<Vertex> path = Dijkstra.getShortestPathTo(v);
                  System.out.println("Path: " + path);
               }
               //buildVisual1();
            }
               
                catch(NumberFormatException g)
               {
                  JOptionPane.showMessageDialog(null,
                        "Not all entries are valid.", "Input Error",
                        JOptionPane.ERROR_MESSAGE);
               }
         }
      }
      
   }
   

 import java.util.PriorityQueue;
 import java.util.List;
 import java.util.ArrayList;
 import java.util.Collections;
 
 public class Dijkstra 
   {
  
   
   
       public static void computePaths(Vertex source)
       {
          source.minDistance = 0.;
          PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
         vertexQueue.add(source);
      
         while (!vertexQueue.isEmpty()) {
            Vertex u = vertexQueue.poll();
         
            // Visit each edge exiting u
            for (Edge e : u.adjacencies)
             {
            

public class Edge
   {
   
      public final Vertex target;
   
      public final double weight;
   
       public Edge(Vertex argTarget, double argWeight)
      
      { target = argTarget; weight = argWeight; }
   
   }

import java.util.Collections;
public class Vertex implements Comparable<Vertex>
   {
      public final String name;
      public Edge[] adjacencies;
      public double minDistance = Double.POSITIVE_INFINITY;
      public Vertex previous;
      public Vertex(String argName) 
		 { 
		 	name = argName; 
		 }
   
       public String toString() 
		 { 
         return name; 
		 }
   
       public int compareTo(Vertex other)
      {
         return Double.compare(minDistance, other.minDistance);
      }
   }

[macosxnerd101]

Your approach seems to be converting between 2D array model vs. Graph<E> model as my tutorial described. Just stick with generic Graph the way my tutorial showed for painting, and draw your Edges and Vertices by subclassing a JComponent like JPanel and overriding paint(). Pick a coordinate to start at and draw your first Vertex. From there, draw the other Vertices at corresponding (scalar) distances and connect the dots. It shouldn't be that hard to paint over the shortest path with a red line.

You can use tools in the java.awt.geom package to model Vertices (or just the Graphics drawOval() method), as well as the Graphics and Graphics2D classes.