?
Solved

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

Posted on 2007-12-02
3
Medium Priority
?
473 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
[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
  • Learn & ask questions
3 Comments
 
LVL 24

Accepted Solution

by:
sciuriware earned 2000 total points
ID: 20394529
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

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

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

741 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