import java.awt.*; import java.awt.event.*; import java.awt.geom.*; import java.util.Vector; class Node { public int x,y; public Path paths[] = new Path[20]; public int nb_paths; } class Path { public int dest; public int value; } class ShortestPath { //main function public static void main(String[] args) throws Exception { FrameApp tf = new FrameApp(); WindowListener listener = new WindowAdapter() { public void windowClosing(WindowEvent e){ System.exit(0); } }; tf.addWindowListener(listener); while (true) { if (tf.redraw) { tf.repaint(); tf.redraw = false; } } } } class FrameApp extends Frame implements ActionListener { static Node somas[] = new Node[20]; static Path paths[] = new Path[20]; static int nb_node = 0, box = 0; static boolean dialog, redraw = false; static TextField textField1, textField2, textField3; static Button button, button2; static Dialog dialogBox; public FrameApp() { setTitle("Dijkstra Algorithm"); setSize(320, 240); Menu File = new Menu("File", true); File.add("Reset"); File.add("Exit"); File.addActionListener(this); Menu Add = new Menu("Add", true); Add.add("Node"); Add.add("Edge"); Add.addActionListener(this); Menu Algo = new Menu("Algorithm", true); Algo.add("Dijkstra"); Algo.addActionListener(this); MenuBar mbar = new MenuBar(); // Create menu bar and add the menus. mbar.add(File); mbar.add(Add); mbar.add(Algo); setMenuBar(mbar); // Add the menu bar to the frame. setResizable(false); setVisible(true); } public void AddNode() { somas[nb_node] = new Node(); dialogBox = new Dialog(this, "new node", false); dialogBox.setLayout(new GridLayout(3,2)); Label text1 = new Label("Enter Position x:"); Label text2 = new Label("Enter Position y:"); textField1 = new TextField("", 3); textField2 = new TextField("", 3); button = new Button("Ok"); button.addActionListener(this); dialogBox.add(text1); dialogBox.add(textField1); dialogBox.add(text2); dialogBox.add(textField2); dialogBox.add(button); dialogBox.resize(260,100); dialogBox.setLocation(30,70); box = 1; Active_Box(); } public void AddPath() { dialogBox = new Dialog(this, "new edge", false); dialogBox.setLayout(new GridLayout(4, 2)); Label text1 = new Label("Enter Node 1:"); Label text2 = new Label("Enter Node 2:"); Label text3 = new Label("Enter Value :"); textField1 = new TextField("", 3); textField2 = new TextField("", 3); textField3 = new TextField("", 3); button = new Button("Ok"); button.addActionListener(this); dialogBox.add(text1); dialogBox.add(textField1); dialogBox.add(text2); dialogBox.add(textField2); dialogBox.add(text3); dialogBox.add(textField3); dialogBox.add(button); dialogBox.resize(260, 135); dialogBox.setLocation(30, 54); box = 2; Active_Box(); } public void actionPerformed(ActionEvent ae) { String arg=ae.getActionCommand(); if (arg.equals("Exit")) System.exit(0); if (arg.equals("Dijkstra") && (nb_node > 1)) Dijkstra(-1); if (arg.equals("Result")) { int node = Integer.parseInt(textField1.getText())-1; if (node < 0 || node >= nb_node) System.out.println("Wrong node Index"); else { dialogBox.hide(); box = 0; Dijkstra(node); } } if (arg.equals("Reset")) { for (int i = 0; i < nb_node; i++) somas[i].nb_paths = 0; nb_node = 0; redraw = true; } if (arg.equals("Node") && (!dialog) && (nb_node < 20)) AddNode(); if (arg.equals("Edge") && (!dialog) && (nb_node > 1)) AddPath(); if (arg.equals("Ok")) { if (box == 1) { somas[nb_node].x = Integer.parseInt(textField1.getText()); somas[nb_node].y = Integer.parseInt(textField2.getText()); if ((somas[nb_node].x < 0) || (somas[nb_node].x > 100) || (somas[nb_node].y > 100) || (somas[nb_node].y < 0)) System.out.println("Wrong Input: Range is [0..100]"); else { somas[nb_node].x *= 3.2; somas[nb_node].y *= 2; somas[nb_node].y += 40; System.out.println("Add a node at position x=" + somas[nb_node].x + " y=" + somas[nb_node].y); dialogBox.hide(); nb_node++; box = 0; redraw = true; } } if (box == 2) { int index = Integer.parseInt(textField1.getText()) - 1; int dest = Integer.parseInt(textField2.getText()) - 1; if ((index < 0) || (index > nb_node) || (index == dest) || (dest < 0) || (dest > nb_node)) System.out.println("Wrong Input! Somas doesn't exist."); else { int val = Integer.parseInt(textField3.getText()); if (val < 0) System.out.println("Value must be positive"); else { somas[index].paths[somas[index].nb_paths] = new Path(); somas[index].paths[somas[index].nb_paths].dest = dest; somas[index].paths[somas[index].nb_paths].value = val; somas[dest].paths[somas[dest].nb_paths] = new Path(); somas[dest].paths[somas[dest].nb_paths].dest = index; somas[dest].paths[somas[dest].nb_paths].value = val; System.out.println("Add an edge between Node " + index + " and Node " + dest + " with value " + val); somas[index].nb_paths++; somas[dest].nb_paths++; dialogBox.hide(); box = 0; redraw = true; } } } if (box == 3) { dialogBox.hide(); box = 0; redraw = true; } } } public void paint(Graphics g) { int radius = 10; g.setFont(new Font("Comic", Font.BOLD, 12)); for (int i = 0; i < nb_node; i++) { g.setColor(new Color(255, 0, 0)); g.fillOval(somas[i].x, somas[i].y, radius * 2, radius * 2); g.setColor(new Color(0, 0, 0)); g.drawString("" + (i+1), somas[i].x + radius/2, somas[i].y + (radius*3/2)); for (int j = 0; j < somas[i].nb_paths; j++) { g.setColor(new Color(0, 0, 255)); g.drawLine(somas[i].x + radius, somas[i].y + radius, somas[somas[i].paths[j].dest].x + radius, somas[somas[i].paths[j].dest].y + radius); g.setColor(new Color(0, 0, 0)); g.drawString("" + somas[i].paths[j].value, (somas[i].x + somas[somas[i].paths[j].dest].x + (2 * radius)) / 2, (somas[i].y + somas[somas[i].paths[j].dest].y + (2 * radius)) / 2); } } } public void Dijkstra(int index) { dialogBox = new Dialog(this, "Dijkstra", false); dialogBox.setLayout(new GridLayout(2 + nb_node, 2)); Label text1 = new Label("Enter Node:"); Label nodes[] = new Label[nb_node]; Label res[] = new Label[nb_node]; textField1 = new TextField("", 3); button = new Button("Ok"); button.addActionListener(this); button2 = new Button("Result"); button2.addActionListener(this); dialogBox.add(text1); dialogBox.add(textField1); Dijkstra a = new Dijkstra(); if ((index != -1) && (somas[index].nb_paths != 0)) a.Algorithm(somas, nb_node, index); for (int i = 0; i < nb_node; i++) { nodes[i] = new Label("" + (i+1) + ":"); dialogBox.add(nodes[i]); if (index == -1) res[i] = new Label(""); else { if (a.result[i]==-1) res[i] = new Label("inf"); else res[i] = new Label("" + a.result[i]); } dialogBox.add(res[i]); } dialogBox.add(button2); dialogBox.add(button); dialogBox.resize(220, 80 + (nb_node*30)); dialogBox.setLocation(30, 20); Active_Box(); box = 3; } public void Active_Box() { dialogBox.show(); WindowListener diag = new WindowAdapter() { public void windowClosing(WindowEvent e) { dialogBox.hide(); redraw = true; } }; dialogBox.addWindowListener(diag); } } class Dijkstra { int result[] = new int[20]; int previous[] = new int[20]; public void Algorithm(Node m_node[], int nb, int start) { for (int i = 0; i < nb; i++) { result[i] = -1; //Set each distance to infinity. previous[i] = -1; //Set each previous node to undefined. } System.out.println("Starting Dijkstra Algorithm from node " + start); result[start] = 0; //Initial node, dist set to 0. Vector vec1 = new Vector(); Vector vec2 = new Vector(); for (int i = 0; i < nb; i++) vec1.add(new Integer(i)); //Add all elements except start to the vector while (!vec1.isEmpty()) { int u = SmallestDist(vec1, nb); if (u == -1) return; vec1.removeElement(new Integer(u)); vec2.add(new Integer(u)); for (int i = 0; i < m_node[u].nb_paths; i++) { int v = m_node[u].paths[i].dest; if (((result[u] + m_node[u].paths[i].value) < result[v]) || (result[v] == -1)) { result[v] = result[u] + m_node[u].paths[i].value; previous[v] = u; } } } } int SmallestDist(Vector vec, int nb) { int tmp = 10001; int index = -1; for (int i = 0; i < nb; i++) { if ((tmp > result[i]) && (result[i] != -1) && (vec.contains(new Integer(i)))) { tmp = result[i]; index = i; } } return index; } }