Solved

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

Posted on 2007-12-02
3
467 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

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
sql import cannot be resolved jsp 3 45
jmss example java 2 23
Java basic valueOf question 1 29
Eclipse Java import and method not resolved 4 48
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
The viewer will learn how to implement Singleton Design Pattern in Java.

856 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