Solved

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

Posted on 2007-12-02
3
466 Views
Last Modified: 2012-06-27
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;

    Vector<TreeMap<Integer,Integer>> adjList;
   

        public Graph(int n) {
        numVertices = n;
        numEdges = 0;
      //  adjMatrix = new int[n][];
        adjList = new Vector<TreeMap<Integer,Integer>>();
        for (int i=0; i<numVertices; i++) {
            adjList.add(new TreeMap<Integer,Integer>());
        }
    }

    public int getNumVertices() {
        return numVertices;
    }

    public int getNumEdges() {
        return numEdges;
    }

    public int getEdgeWeight(Integer v, Integer w) {
        return adjList.get(v).get(w);
    }

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

    public void addEdge(Edge e) {
        Integer v = e.getV();
        Integer w = e.getW();
        int weight = e.getWeight();
        addEdge(v,w,weight);
    }

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

    public Edge findEdge(Integer v,Integer w) {
        int wgt = adjList.get(v).get(w);
        return new Edge(v,w,wgt);
    }

    TreeMap<Integer,Integer> getAdjList(Integer v) {
        return adjList.get(v);
    }

}


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++) {
            mark[v] = g.adjList.indexOf(0,v);
            if (mark[v] == -1) {
                //System.out.println(mark[v]);
                search(v);
            }
        }
        iter = 0;
    }

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

class Tester {
    public static void main (String args[]) {
        Graph g = new Graph(6);
        g.addEdge(1,2,50);
        g.addEdge(1,3,40);
        g.addEdge(2,5,150);
        g.addEdge(2,4,60);
        g.addEdge(3,4,75);
        g.addEdge(4,5,87);
        g.addEdge(5,1,300);
        g.addEdge(1,4,200);
        g.addEdge(3,5,75);
        iterator irt = new iterator(g);
        irt.startSearch();
 }
}
0
Comment
Question by:mateo6281
3 Comments
 
LVL 24

Accepted Solution

by:
sciuriware earned 500 total points
ID: 20394529
0

Featured Post

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

Question has a verified solution.

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

Suggested Solutions

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…
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:

821 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question