Connect points from a file - Shortest Path

Question

I have an application that reads in a set of points and plots them on a JPanel. I am now wanting to modify that code so that it draws a line in between each of the points. Here is my code for just plotting the points.

Code:

import javax.swing.*;
import java.awt.*;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;

public class Test {

    private static final String FILE = "Desktop/Test1.txt";
    private static Point[] points;

    public static void main(final String[] args){
        try{
            final BufferedReader br = new BufferedReader(new FileReader(new File(FILE)));
            points = new Point[Integer.parseInt(br.readLine())];
            int i = 0;
            int xMax = 0;
            int yMax = 0;
            while(br.ready()){
                final String[] split = br.readLine().split("\t");
                final int x = Integer.parseInt(split[0]);
                final int y = Integer.parseInt(split[1]);
                xMax = Math.max(x, xMax);
                yMax = Math.max(y, yMax);
                points[i++] = new Point(x, y);




            }
            final JFrame frame = new JFrame("Point Data Rendering");
            final Panel panel = new Panel();
            panel.setPreferredSize(new Dimension(xMax + 10, yMax + 10));
            frame.setContentPane(panel);
            frame.pack();
            frame.setVisible(true);
            frame.repaint();
        } catch (final Exception e){
            e.printStackTrace();
        }
    }

    public static class Panel extends JPanel {

        @Override
        public void paintComponent(final Graphics g){
            g.setColor(Color.RED);
            for(final Point p : points){
                g.fillRect((int) p.getX(), (int) p.getY(), 2, 2);
            }
        }

    }

}

If anyone has any cool algorithms that finds the shortest path to connect all the dots, I would be very interested in learning them!

Answer 1

Finding the shortest path to connect all the dots is known as the Travelling Salesman Problem, and is known as NP-hard. Basically this means that there's no fast algorithm that finds the SHORTEST path. However, there are fast algorithms that find a pretty short path, and on top of that, if the number of dots is very small (10 or less) then you can conceivably enumerate all possible solutions.

A very very simple algorithm is to start with a random point, calculate the distance to each point and pick the path that's the shortest, and repeat until you've visited every point. To make this slightly smarter, you can then go along the path and attempt to exchange every two lines (e.g. if you do a-B B-c c-D try a-c c-B B-D) and keep it if it makes the path shorter.

Read about the Travelling Salesman Problem here: http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms