Dijkstra's Algorithm With Priority Queue - Method To Find Minimum Distance Is Nonfunctional
May 14, 2014
I was given some code by a professor to add some features to as part of an assignment. However, the code itself doesn't seem to work.
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
public class DijkstraPriorityQueue
[Code] ....
The method to find minimum distance is nonfunctional...I receive an error that the types are incompatible. I can't do the assignment if the base code doesn't work to begin with...
View Replies
ADVERTISEMENT
Jan 5, 2015
I have to implement Dijkstra algorithm in Java.
Input file looks like this:
3
5
1 5 1
4 5 3
3 4 5
4 3 7
1 6 9
2 5 12
2 6 3
5 4 4
First and second numbers are in order source and destination points.
First and second numbers in another each line represent edges. Third one is wage of each edge.
My code looks as follows:
import java.util.*;
import java.io.*;
class Vertex implements Comparable<Vertex>
{
public int name = 0;
public ArrayList<Edge> adjacencies = new ArrayList<Edge>();
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
[Code] .....
View Replies
View Related
Apr 15, 2014
Implement a priority queue based on a sorted linked list. The remove operation on the priority queue should remove the item with the smallest key.
View Replies
View Related
May 6, 2014
I'm trying write a Dijkstra's implementation in java. First off, here is the algorithm:
package lab3;
import java.util.HashMap;
import java.util.Stack;
/**
* Compute shortest paths in a graph.
*
* Your constructor should compute the actual shortest paths and maintain all the information needed to reconstruct them. The returnPath() function should use this information to return the appropriate path of edge ID's from the start to the given end.
*
* Note that the start and end ID's should be mapped to vertices using the graph's get() function.
*/
class ShortestPaths {
Multigraph graph;
final int INF = Integer.MAX_VALUE;
PriorityQueue<Integer> Q;
[Code] ....
I followed someone else psuedocode very closely but for whatever reason, my edge[] array is just full of null data, which means I can't actually return the shortest path. Why that's happening/how to fix it? Maybe I'm not understanding dijstra's correctly.
View Replies
View Related
Nov 28, 2014
I have a class "ExecuteJob" which has Print Q in the form of Priority Q.
You can keep adding job to the Q by calling one of the method in the class. However, and object cant do things simultaneity can it? While im adding a new job to the print queue, can it be executing and existing job in the print Q.
To achieve that, I would need to implement process and threads? I believe am I right? So that adding a job is independent to being removed?
View Replies
View Related
Dec 4, 2014
I am in the process of implementing Priority queue, as I understand that there are many data structures you could use to implement. I implemented it with the an array, which it works absolutely fine. However I have limitations on what collections I can use from the collections classes. I fact I cant use any of the collections classes. Meaning I cant use array.
I’m trying to implement Priority Queue using heap. And implementing heap using binary trees. But however I have a few questions which I need to clarify and I cant think of any other way of resolving it. Ofcourse I can implement my own simple array class using linked list.
Inserting into heap would be quite simple, as I just need to find the right last position from left to right leaf to insert the node into the tree. However after inserting, you may want to make sure that leaf node values are > than root node. Therefore, the root node will always be with the highest priority.
I call these steps where you compare from top down as bubbledown and bubbleup. To do this I really need a for each node within the treee node to have attribute pointing to its root node. So in case of bubbleup I always have a pointer for a given node to its root, without it would mean I would to traverse through the entire tree to identify its root. Which I believe is very inefficient.
Or have I taken this completely wrong? Or is it the case that heap are only best with arrays and therefore use array (by implement it using linked list?)
View Replies
View Related
Mar 30, 2014
I have a PriorityQueue called incoming, containing objects of type Vehicle.
All vehicles have a fuel level, that can be accessed by the getter method getFuelLevel().
I want to be able to choose to sort the queue so that the Vehicles with the lowest fuel levels are at the front of the queue.
View Replies
View Related
May 11, 2014
I am using the shortest path algorithm to determine the connection between individuals within a given array. The array is written into the code and not read from external files.
When I am having problem is .. i am having problems how to prompt the user for the starting point or vertex and read that prompt to determine the starting point in the array. I know that this code :
computePaths(v0);
determines the starting point. i want to read "v0" from the user prompt.
total code being used
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.io.IOException;
import java.util.Scanner;
class Vertex implements Comparable<Vertex>
[Code] .....
View Replies
View Related
May 4, 2014
I'm working on a lab for my class. I need to create a Priority Queue in Java using an array list. The kicker is that each node has to have a "handle" which is just an object which contains the index of of the node that it's associated with. I know that sounds weird but we have to implement it this way. Anyway, my priority queue seem to work fine except the handle values apparently aren't updating correctly because I fail the handle test. Also, I run into problems with handles only after extractMin() is called, so I figured the problem would be somewhere in that method but I've been through it a million times and it looks good to me.
Here is my Priority Queue Class:
package lab3;
import java.util.ArrayList;
/**
* A priority queue class supporting operations needed for
* Dijkstra's algorithm.
*/
class PriorityQueue<T> {
final static int INF = 1000000000;
ArrayList<PQNode<T>> queue;
[Code] ....
I can post the tests too but I don't know if that would do much good. Just know that the queue works as is should, but the handles don't point to the right nodes after extractMin() is utilized.
View Replies
View Related
Oct 9, 2014
My assignment was to create a priority queue for Airline Passengers. Here is what I have done so far:
//Driver
package priorityqueuestandby;
import java.util.NoSuchElementException;
import javax.swing.JOptionPane;
public class PriorityQueueStandBy {
public static void main(String[] args) {
[Code] .....
So the part that I cant figure out is:
When a standby passenger is to be enqueued into the priority queue, it must be done so that at the moment of each dequeue operation, the item at the head of the queue is the standby passenger with the longest longevity, and also so that passengers with the same longevity are dequeued in a first-come-first-served fashion.
he says that we need to "Make your program so that it extends Comparable and implements the compareTo() method properly..."
So I was looking at the Comparable class and I could't find a compareTo() method... I am not confident I know how extends works either. I am assuming I need a new class if I am going to be extending another class. Right now I am taking in longevity as a String and converting it to an int because my last ditch effort is going to be to set up a loop that will organize longevity into a/an circular array based on the size of the incoming integer.
View Replies
View Related
Sep 27, 2013
I have been having difficulty with the weeks concepts in my online Java class, the program is to be as followed:
For this exercise you will implement a class called Pair, that represents a pair of two numbers.The Pair class should include the following constructor and methods:
CONSTRUCTORS
public Pair(double num1, double num2) -- Creates an object that represents a pair of double values
METHODS
public double getAverage() -- Returns the average value of the two numbers
public double getDistance() -- Returns the absolute vale of the distance between the two numbers
public double getMaximum() -- Returns the maximum value of the two numbers
public double getMinimum() -- Returns the minimum vale of the two numbers
Write a class called PairTest that tests your Pair implementation. The PairTest should prompt the user for the two values, create a Pair object with the values and then print the average, distance, maximum, and minimum of the pair. The input / output should look like the following:
Enter the first number: 5.5
Enter the second number: 3.0
Average: 4.25
Distance: 2.5
Maximum: 5.5
Minimum: 3.0
NOTE: For this exercise, your solution should not use any conditional statements. Instead you should use the methods provided by thejava.util.Math.
So far I have:
import java.lang.Math;
import java.util.Scanner;
public class Main
{
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
{
System.out.println("Please enter a value for the first number");
[Code] ....
View Replies
View Related
Apr 27, 2014
I have been looking around and I cannot seem to find which algorithm java uses for its sort method. Merge, sort etc.
While I am on the topic BinaryTree is a balanced heap right?
Are there any libraries for depth or breath first search?
Is the ArrayList a double linked list?
View Replies
View Related
May 14, 2014
you need to find out the distance between two trains using only two commands
mf - move forward
mc - move backward
the trains are dropped using helicopter by parachutes . both doesn't know where they are; no gps in the train they are in the same track
write a code to find the trains using the given commands
View Replies
View Related
Sep 19, 2014
Pretty much what im trying to accomplish, i need to write a program that figures out the distance between one point to another, using miles and feet..
Heres how it has to look: "The distance from my uncles house is ___ miles, or ____ feet."
I can get it to run if i add only whole miles..but when i try to add 8.5 miles, and compile, the program flips out..I know i need to use a double somewhere, but cant figure it out, here is my code..
import java.util.Scanner; //required for input
public class feetToMiles {
public static void main (String[] args){
//Create new scanner object called input
Scanner input = new Scanner (System.in); //allows for input
[Code] ....
View Replies
View Related
Mar 20, 2015
I am using the following code: But doesn't work fine. I try to find the Minimum spanning and print it out from house to which hose.
public class MinimumSpanning {
public static void main(String[] args) {
// [][] edge= are price between each hose edgs.
int [][] edge= {{0,7,9,12,0,0,0},
{7,0,0,10,0,0,0},
{10,0,0,12,0,0,0},
{12,10,12,0,11,0,10},
{0,0,0,11,0,4,8},
{0,0,0,0,4,0,6},
{0,0,0,10,8,6,0}};
[code]....
It should only print one time. Example between K to L prints many time.
View Replies
View Related
Jan 26, 2014
I finished a game in Java and sent it to a friend. Launching the program in my computer worked just fine.
But he got this error : "Could not find the main classs: Main. program will exit"
My JRE version is the most updated one. His JRE was version 1.6. He updated his JRE, and the problem was solved.
This is a bit worrying for me, because as far as I know, 1.6 isn't a very old version of the JRE. It's not the most recent one, but not that old.
This is worrying because I'm planning on sending my game to a lot of friends, and trying to distribute it on the internet.
A lot of people don't have the most updated JRE. And they are mostly non-programmers, so I can't expect them to update to the newest version of Java upon downloading my game. They might not know what Java is, even though they got it on their computer, and upon receiving an error, they'll just give up on the game.
If my game wouldn't work with a significantly old JRE, that would be reasonable. It's part of the nature of working with Java. But the fact that a relatively updated JRE, 1.6, doesn't work with my game, is worrying.
*(Please note: My game isn't implementing anything "special". Swing and KeyBindings are the 'newest' additions to Java that I can think of inside my game)*.
In short, I'd like to know that my game works on most of the computers it tries to run on. Knowing that it doesn't work on a relatively new JRE, is worrying.
So I have two questions:
1. Is it normal, for a Java program, to have such "high" demands for the JRE version? Do a lot of Java games demand at least version 1.6 of the JRE? Is this common?
2. How can I find out the minimum JRE version requirement for my program? Is there a methodical way to do this, or do I just have to go through all the libraries I use in my game and figure out what's the JRE release version for each one?
View Replies
View Related
Feb 3, 2014
I'm required to create a program that finds the minimum value in an Array of integers.
Here is my approach :
public class Person {
public static void main(String [ ] args){
int theArray[]=new int [10];
int result = 0;
for (int i:theArray){
if (i < Integer.MAX_VALUE)
[Code]...
I can't really progress from this position. I keep getting told to change the return type to int on main method, then when i do it says change it to void..
View Replies
View Related
Feb 20, 2015
Write method distance, which calculates the distance between two points (x1, y1) and (x2, y2). All numbers and returned values should be of type double. Incorporate this method into an program that enable the user to enter the coordinates of the points, then calculate and display the distance by calling the method –distance.
I've tried numerous times to make it work and I'm on the right path, however I'm missing some things in the code to make my results look like this later on, which I've attached onto this post.
View Replies
View Related
Mar 13, 2015
I need to modify the drawShape method to calculate the distance from the starting point (the diameter) of any shape regardless of how many sides I give it, but I have absolutely no clue where to begin with this. The ultimate goal of the program is to calculate the value of pi using the shape that is drawn.
Java Code:
public class PiTurtle extends Turtle
{
private double mySize;
private int mySides;
private double diameter = 0;
[code]....
View Replies
View Related
Apr 13, 2014
I am trying to write a loop that calculates the distance traveled (distance = speed * time). It should use the loop to calc how far the vehicle traveled for each hour of time. My program asks for hours and then mph but its not calculating time * speed. Here is my code.
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Enter Hours Traveled ");
int hoursTraveled = input.nextInt();
System.out.println("Enter MPH ");
int mph = input.nextInt();
[Code] .....
View Replies
View Related
Oct 18, 2014
I've just been having a go at an exercise where I have to create and use a class called Point, with two fields of type double. I have to create some methods for it, one of which is a distanceTo(Point) method, that calculates the distance to another point. I've tried to keep the distanceTo(Point) method short so have created some other methods to use within the method. My question is about the getDistance() method that I've made. As you can see below, I've given it two parameters, which are references to values within two Point objects (this.x and otherPoint.x).
double distanceTo(Point otherPoint) {
double distanceX = getDistance(this.x, otherPoint.x);
double distanceY = getDistance(this.y, otherPoint.y);
return calculateLength(distanceX, distanceY);
}
View Replies
View Related
Mar 24, 2014
What would be a good and simple algorithm to find the shortest route between two points in a 2D array[grid] ? There can be certain obstacles in the grid i.e. some of the cells may be inaccessible. I tried googling for it and found that A* is the best for this but I am just a beginner and would like to start with something much simpler.
View Replies
View Related
Nov 15, 2014
I've created a getMin method to return the smallest value in a queue. However, I'm having trouble calling the method in my main.
/**
* Main method.
*
* @param args
* the command line arguments; unused here
*/
public static void main(String[] args) {
SimpleReader in = new SimpleReader1L();
SimpleWriter out = new SimpleWriter1L();
Queue<Integer> testQueue = new Queue1L<Integer>();
[Code] .....
View Replies
View Related
Apr 19, 2015
The question is write to a method symmetric that accepts a stack of integers as a parameter and replaces the stack contents with itself plus a symmetrical version of itself (the same elements in the opposite order).
For example, suppose a variable s stores the following elements:
bottom [10, 50, 19, 54, 30, 67] top
After a call of symmetric(s),the stack would store the following elements
bottom [10, 50, 19, 54, 30, 67, 67, 30, 54, 19, 50, 10] top
Note that the symmetric version is added on to the top of what was originally in the stack. The bottom half of the stack contains the original numbers in the same order.
If your method is passed an empty stack, the result should be an empty stack.
If your method is passed a null stack, your method should throw an IllegalArgumentException.
a) Write the method symmetric using one temporary stack and one temporary queue.
/> Re-write the method using only one temporary Queue.
What I have done so far is
public static Stack symmetric(Stack s1){
Stack s2 =new Stack();
int theTop=0;
if(s1.isEmpty()){
return s1;
[Code] .....
Its not working.
View Replies
View Related
Oct 21, 2014
So I have to write all the methods for a LinkedListQueue. I've got isEmpty, enqueue and dequeue working correctly (I think) but I'm having trouble with the toString method. I tried to do it recursively and it works if there is only one element in the list, but with multiple elements it throws a StackOverflowerror exception. I've tried it multiple different ways, but I can't seem to figure out how to print it out with out clearing everything. We haven't been taught StringBuilder or .append yet, which I saw a lot of as I was looking for solutions, so I can't use those.
public class LinkedQueue<T>
{
protected LLNode<T> front; // reference to the front of this queue
protected LLNode<T> rear; // reference to the rear of this queue
private T info;
public LinkedQueue()
{
front = null;
rear = null;
[Code] ....
and this is the ITD used with it, for some reason it has the "empty the queue" function as a choice but we weren't assigned that function, so just ignore it.
import java.util.Scanner;
public class ITDLinkedQueue
{
public static void displayMenu()
{
System.out.println("(1) display menu");
System.out.println("(2) check isEmpty");
System.out.println("(3) enqueue");
System.out.println("(4) dequeue");
[Code] ....
View Replies
View Related
Dec 1, 2014
This was shown in class the other day and I'm still not sure of how exactly it works, even after looking at it through a debugger.
public void sort(){
for (int i = 0; i < size; i++) {
Node temp1 = head;
Node temp2 = head;
Node temp3 = head;
while(temp2.next!=null){
temp3 = temp2.next;
[Code]...
Again, I didn't write this code I'm just trying to understand it. Why specifically do three different temp values need to be used instead of just one like in most sorts?
It is part of a larger program that can be found below.
import java.util.Random;
public class MyQueue implements IntegerQueue{
class Node{
Node next;
Integer data;
Node(Integer data){
this.data = data;
[Code]....
View Replies
View Related
