5 Replies - 2241 Views - Last Post: 04 April 2014 - 11:37 PM Rate Topic: -----

#1 AMDee   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 85
  • Joined: 17-December 13

Involving Dijkstra's algorithm

Posted 04 April 2014 - 05:29 PM

Hey all,

I am having problems starting my assignment. I was wondering if anyone could help me. I have attached the assignment so you guys can view it. I just need some guidance through this assignment. I am usual quick to learn. I am planning to do a arraylist instead of linklist.
This is my code so far...

Vertex Class
public class Vertex
{
    String vertexName;
}



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

public class Graph
{
    public static String readFile()
    {
        File mapping = new File("mapping.txt");

        Scanner input = null;
        try
        {
            input = new Scanner(mapping);
        }catch(FileNotFoundException e){
            System.out.println("Sorry, that file name is not found");
        }  

        String dataFile = "";
        while(input.hasNext())
        {
            dataFile += input.next();
        }

        return dataFile;
    }

    public void useAlgorithm(Vertex startVertex,Vertex endVertex)
    {

    }

    public String toString()
    {
        return "hey";
    }

    public static void main(String[]args)
    {

        System.out.println(readFile());
    }
}



Edge Class
public class Edge
{
   String startVertices;
   String endVertices;
   Double edge;
}



MappingApp Class
public class MappingApp
{
    public static void main (String[]args)
    {
        
    }
}



Background Information
Have you ever wondered how websites like Google Maps can give you directions from point A to point B? One solution involves the use of graph theory and a well-known procedure known as Dijkstra’s algorithm.
First, some basics! As you may have learned from your math classes, a graph is just a collection of vertices (also known as nodes) that may be connected by edges. In a weighted graph, these edges are associated with numerical values. Think of the vertices as representing particular locations, and the edges as representing the distance (or more generally, “cost” of traveling) between two vertices.
Here’s an example of what a simple graph might look like (not drawn to scale):

Attached File(s)

  • Attached File  A.pdf (219.94K)
    Number of downloads: 325


Is This A Good Question/Topic? 0
  • +

Replies To: Involving Dijkstra's algorithm

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12653
  • View blog
  • Posts: 45,829
  • Joined: 27-December 08

Re: Involving Dijkstra's algorithm

Posted 04 April 2014 - 06:02 PM

A few points.
  • The Graph class shouldn't be responsible for File I/O. A separate class should be used to handle reading in the data. The Graph class should just model the Graph.

  • You're missing some instance variables in your Vertex class. Aside from what was mentioned in your PDF, I would include a List<Edge> instance variable to record the incident edges. This will make lookup and graph traversal more efficient.

  • For your Edge class, I would use actual Vertex objects rather than names, as it eliminates the need to handle lookups.


Now do you understand how Dijkstra's algorithm works?
Was This Post Helpful? 1
  • +
  • -

#3 AMDee   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 85
  • Joined: 17-December 13

Re: Involving Dijkstra's algorithm

Posted 04 April 2014 - 06:32 PM

*Didn't the paper say the Graph class should load the file? Isn't what I'm doing right now considered loading it?

*Could you list these instance variables? I would have a good idea of what I'm doing.

*So name of the vertex object?

* I actually read your post about Dijkstra's algorithm's but sadly I did not get it.. However, it did give me an insight. The youtube video https://www.youtube....h?v=8Ls1RqHCOPw helped me understand a bit though.

This post has been edited by andrewsw: 04 April 2014 - 06:43 PM
Reason for edit:: Removed previous quote

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12653
  • View blog
  • Posts: 45,829
  • Joined: 27-December 08

Re: Involving Dijkstra's algorithm

Posted 04 April 2014 - 11:25 PM

Quote

Didn't the paper say the Graph class should load the file? Isn't what I'm doing right now considered loading it?

I honestly skimmed the PDF. In re-reading it, those seem to be the instructions. Though in all fairness, it's not a very good design. Definitely do what the instructions say, but just note this is poor practice for future programs.

Quote

Could you list these instance variables? I would have a good idea of what I'm doing.

Your PDF listed most of them. The List<Edge> is one I'd add.

Quote

So name of the vertex object?

No. A reference to the Vertex object would be in the Edge, rather than just a String denoting its name.

Quote

I actually read your post about Dijkstra's algorithm's but sadly I did not get it.

Dijkstra's algorithm is essentially a greedy BFS. You start at the given vertex and push its incident edges onto the heap. You then poll the minimum cost edge, update the cost on the incident neighbor vertex, and repeat.
Was This Post Helpful? 1
  • +
  • -

#5 AMDee   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 85
  • Joined: 17-December 13

Re: Involving Dijkstra's algorithm

Posted 04 April 2014 - 11:33 PM

View Postmacosxnerd101, on 05 April 2014 - 12:25 AM, said:

Your PDF listed most of them. The List<Edge> is one I'd add.


Could you give me a code sample of how the list<Edge> looks like
and how I could use it?

This post has been edited by AMDee: 04 April 2014 - 11:44 PM

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12653
  • View blog
  • Posts: 45,829
  • Joined: 27-December 08

Re: Involving Dijkstra's algorithm

Posted 04 April 2014 - 11:37 PM

You literally replace the Strings with Vertex objects and traverse the Graph in a similar manner as a Linked List.

I wrote a Graphs tutorial a while back. The terminology is a bit flopped. The "Connector" class is similar to your Edge. The "Edge" class is actually your vertex. I've never gone back and fixed the terminology, but this should give you some idea of how a graph is structured.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1