Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

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

Posted on 2007-12-02
3
Medium Priority
?
474 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

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

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

Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Suggested Courses

636 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