Solved

I would like to learn how to implement a greedy Dijkstra algoritm in java

Posted on 2007-12-02
Medium Priority
473 Views
I already have a working program that tests a breath first search traversal, I just not sure how to go about implement a Dijkstra greedy algorithm......... here's my code:

import java.util.*;
import java.io.*;
public class Graph {
private int numVertices;
private int numEdges;

public Graph(int n) {
numVertices = n;
numEdges = 0;
for (int i=0; i<numVertices; i++) {
}
}

public int getNumVertices() {
return numVertices;
}

public int getNumEdges() {
return numEdges;
}

public int getEdgeWeight(Integer v, Integer w) {
}

public void addEdge (Integer v, Integer w, int wgt) {
numEdges++;
}

Integer v = e.getV();
Integer w = e.getW();
int weight = e.getWeight();
}

public void removeEdge(Edge e) {
Integer v = e.getV();
Integer w = e.getW();
numEdges--;
}

public Edge findEdge(Integer v,Integer w) {
return new Edge(v,w,wgt);
}

}

}

class Edge<E> {
private Integer v, w;
private int weight;

public Edge (Integer first, Integer second, int edgeWeight) {
v = first;
w = second;
weight = edgeWeight;
}

public int getWeight() {
return weight;
}

public Integer getV() {
return v;
}

public Integer getW() {
return w;
}
}

class iterator implements Iterator<Integer> {
private Graph g;
private int numVertices;
private int count;
private int[] mark;
private int iter;

public iterator(Graph g) {
this.g = g;
numVertices = g.getNumVertices();
mark = new int[numVertices];
Arrays.fill(mark,0,numVertices,-1);
count = 0;
iter = -1;
startSearch();
}

public boolean hasNext() {
return (iter >= 0) && (iter < numVertices);
}

public Integer next() throws NoSuchElementException {
if (hasNext()) {
return mark[iter++];
}
else {
throw new NoSuchElementException();
}
}

public void remove() {
throw new UnsupportedOperationException();
}

protected void startSearch() {
for (int v=0; v<numVertices; v++) {
if (mark[v] == -1) {
//System.out.println(mark[v]);
search(v);
}
}
iter = 0;
}

protected void search(Integer vertex) {
TreeMap<Integer,Integer> m;
Set<Integer> connectedVertices;
Integer v;
while (!q.isEmpty()) {
System.out.println(q);
v = q.remove();
if (mark[v] == -1) {
mark[v] = count++;
connectedVertices = m.keySet();
//System.out.println(connectedVertices);
for (Integer w : connectedVertices) {
if (mark[w] ==-1) {
}
}
}
}
}
}

class Tester {
public static void main (String args[]) {
Graph g = new Graph(6);
iterator irt = new iterator(g);
irt.startSearch();
}
}
0
Question by:mateo6281
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 24

Accepted Solution

sciuriware earned 2000 total points
ID: 20394529
0

Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
Suggested Courses
Course of the Month15 days, 8 hours left to enroll