0

I am attempting to implement Dijkstra's Algorithm with Java. I am doing so using an ArrayList, and I know that there are other data structures that might be better suited to this task. However, I want to get comfortable with ArrayLists, so that's what I'll be using.

I have an ArrayList of Objects. These objects contain several values, one of which is the distance from the source node. How can I select the node that has the smallest distance value?

I want to then set the name of the vertex that had the smallest distance value to the String "smallest".

Here is what I have so far.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.ArrayList;

public class Graph
{

ArrayList<Vertex> vertexObjects = new ArrayList<Vertex>();
ArrayList<Edge> edgeObjects = new ArrayList<Edge>();
ArrayList<Vertex> visitedObjects = new ArrayList<Vertex>();
ArrayList<Vertex> unvisitedObjects = new ArrayList<Vertex>();
int numVertices = 0;

public void readFile()
{
    try {
        Scanner s = new Scanner(new File("graph.txt"));
        String sameVertex = "";

        while (s.hasNext()) {
            String preVertex = s.next();
            String postVertex = s.next();
            String distance = s.next();

            Edge temp = new Edge(preVertex, postVertex, distance);
            edgeObjects.add(temp);

            if (!(preVertex.equals(sameVertex)))
            {
                Vertex herp = new Vertex(preVertex, Double.POSITIVE_INFINITY, false, null);
                vertexObjects.add(herp);
                sameVertex = preVertex;
                numVertices++;
            }
        }
    } catch (FileNotFoundException e) {
        System.out.println("I can't find that file!");
    }
}

public void Dijkstra(String startVertex, String endVertex)
{
    // Change the distance of the startVertex to 0 and all others to infinity.
    for (int i = (numVertices-1); i >= 0; i--)
    {
        if (vertexObjects.get(i).vertexName.equals(startVertex))
        {
            vertexObjects.get(i).distance = 0;
        } else {
            vertexObjects.get(i).distance = Double.POSITIVE_INFINITY;
        }
        unvisitedObjects.add(vertexObjects.get(i));
    }
    String currentVertex = startVertex;
    //Set the node with lowest distance value to Current Status

    while( unvisitedObjects.size() != 0) {

            {
        //set current node to vertex with shortest distance

        string smallest;
        for (int j = (vertexObjects.size()-1); j >= 0; j++) {
            if (vertexObjects.get(j).distance < 0) {
                smallest = vertexObjects.get(j).distance;
            }

        }
    }

   }
}

public class Vertex
{
    public String vertexName;
    public double distance;
    public boolean visitedStatus;
    public String previousVertex;

public Vertex(String vertexName, double distance, boolean visitedStatus, String previousVertex)
{
    this.vertexName = vertexName;
    this.distance = distance;
    this.visitedStatus = visitedStatus;
    this.previousVertex = previousVertex;
}

public String toString()
{
    String d;
    if (this.visitedStatus = false) 
    {
        d = "unvisited";
    } else {
        d = "visited";
    }
    String s = "Vertex " + vertexName + " is " + d + "and is " + distance + " away from " + previousVertex + ".";
    return s;
}

}

FelixTheNub
  • 181
  • 2
  • 10
  • Have you though about a PriorityQueue? That automatically sorts the edges that need to used to explore the possible paths. Else you should sort the List after editing the list. – martijnn2008 Apr 18 '14 at 21:06
  • I don't really get this. You're asking how to get the min value from an ArrayList? This is one easiest algorithms I can think of to implement. That shouldn't be a problem if you're trying to implement Dijkstra, which is a lot more complicated than that. – wvdz Apr 18 '14 at 21:07
  • Indeed don't try to fix a car's engine with a banana, that makes no sense too. – martijnn2008 Apr 18 '14 at 21:08
  • I can easily think about how to do it if it were an ArrayList of integers, but because the values are simply attributes of an object, I don't know how to go about it. – FelixTheNub Apr 18 '14 at 21:22
  • I figured it out, but I can't post the code because my rep is too low to reply to my own question. – FelixTheNub Apr 18 '14 at 22:16

0 Answers0