I find that there are not a lot of good examples of this with heaps so here is my implementation as a coding example (in java).
First let me define the underlying Vertex/Edge data structure with the following classes:
public class Edge{
public double weight;
public Vertex destination;
public Edge(Vertex destination, double weight) {
this.destination = destination;
this.weight = weight;
}
}
public class Vertex implements Comparable<Vertex>{
public String name;
public ArrayList<Edge> adjacentEdges; //list of outgoing edges
public Double minDistance = Double.POSITIVE_INFINITY; //used for SSP
public Vertex(String name) {
this.name = name;
this.adjacentEdges = new ArrayList<Edge>();
}
public void addEdge(Vertex dest, double cost){
adjacentEdges.add(new Edge(dest, cost));
}
@Override
public int compareTo(Vertex o) {
return (int)(minDistance - o.minDistance); //to be used for heaps
}
}
The graph class creates an adjacency list for nodes provided and a hashmap to prevent node duplication.
public class Graph {
public ArrayList<Vertex> adjacenyList;
HashMap<String, Vertex> vertexMap;
public Graph() {
this.adjacenyList = new ArrayList<Vertex>();
vertexMap = new HashMap<String, Vertex>();
}
public void addNodes(String vertex, String destination, double distance){
//check if vertex already exists
Vertex src = getNodeOrCreate(vertex);
Vertex dest = getNodeOrCreate(destination);
//add edge to vertex
src.addEdge(dest, distance);
}
private Vertex getNodeOrCreate(String node){
Vertex v;
if(vertexMap.containsKey(node)){
v = vertexMap.get(node);
}else{
v = new Vertex(node);
vertexMap.put(node, v);
adjacenyList.add(v);
}
return v;
}
public Vertex getVertexByName(String name){
return vertexMap.get(name);
}
public void printAdjacencyList(){
for(Vertex v : adjacenyList){
System.out.print("Vertex: " + v.name);
for(Edge e : v.adjacentEdges){
System.out.print(" " + e.destination.name + "/" + e.weight);
}
System.out.println();
}
}
//algorithms
public ArrayList<Vertex> depthFirstSearch(Vertex start) {
Vertex head = start;
Stack<Vertex> stack = new Stack<Vertex>();
ArrayList<Vertex> result = new ArrayList<Vertex>(); //visited
stack.push(head);
while (!stack.isEmpty()) {
head = stack.pop();
if (!result.contains(head)) {
result.add(head);
for (Edge e : head.adjacentEdges) {
stack.push(e.destination);
}
}
}
return result;
}
public ArrayList<Vertex> breadthFirstSearch(Vertex start){
Queue<Vertex> queue = new LinkedList<Vertex>();
ArrayList<Vertex> result = new ArrayList<Vertex>(); //visited
Vertex head = start;
queue.add(head);
result.add(head);
while(!queue.isEmpty()){
head = queue.poll();
for (Edge e : head.adjacentEdges){
if(!result.contains(e.destination)){
queue.add(e.destination);
result.add(e.destination);
}
}
}
return result;
}
public Double djksraShortestPath(Vertex src, Vertex dest){
//reset mins
resetMins();
PriorityQueue<Vertex> heap = new PriorityQueue<Vertex>();
//init all edges as infinity
src.minDistance = 0.0;
for(Vertex v : adjacenyList){
heap.add(v);
}
Vertex next;
while(!heap.isEmpty()){
next = heap.poll(); //extract min
for(Edge e : next.adjacentEdges){
Double cost = next.minDistance + e.weight;
if(cost < e.destination.minDistance){
e.destination.minDistance = cost;
}
}
}
return dest.minDistance;
}
public Double djksraShortestPath(String src, String dest){
return djksraShortestPath(getVertexByName(src), getVertexByName(dest));
}
private void resetMins(){
for(Vertex v : adjacenyList){
v.minDistance = Double.POSITIVE_INFINITY;
}
}
}
Its always important to use test frameworks to test code, but since this is a simple console application I do all the verification in main.
public static void complicatedGraph(){
//complicated graph
Graph weightedGraph = new Graph();
weightedGraph.addNodes("A","B", 20);
weightedGraph.addNodes("A","D", 80);
weightedGraph.addNodes("A","G", 90);
weightedGraph.addNodes("B","F", 10);
weightedGraph.addNodes("E","B", 50);
weightedGraph.addNodes("E","G", 30);
weightedGraph.addNodes("G","A", 20);
weightedGraph.addNodes("D","G", 20);
weightedGraph.addNodes("D","C", 10);
weightedGraph.addNodes("F","D", 40);
weightedGraph.addNodes("F","C", 10);
weightedGraph.addNodes("C","F", 50);
weightedGraph.addNodes("C","D", 10);
weightedGraph.addNodes("C","H", 20);
weightedGraph.printAdjacencyList();
ArrayList<Vertex> bfs = weightedGraph.breadthFirstSearch(weightedGraph.getVertexByName("A"));
ArrayList<Vertex> dfs = weightedGraph.depthFirstSearch(weightedGraph.getVertexByName("A"));
System.out.print("BFS ");
printVertexList(bfs);
System.out.print("DFS ");
printVertexList(dfs);
System.out.println("");
System.out.println("Shortest distance between A and H is " + weightedGraph.djksraShortestPath("A", "H"));
System.out.println("Shortest distance between A and E is " + weightedGraph.djksraShortestPath("A", "E"));
System.out.println("Shortest distance between D and H is " + weightedGraph.djksraShortestPath("D", "H"));
}
public static void simpleGraph(){
Graph graph = new Graph();
graph.addNodes("A","B", 1);
graph.addNodes("A","D", 1);
graph.addNodes("A","G", 1);
graph.addNodes("B","E", 1);
graph.addNodes("B","F", 1);
graph.addNodes("E","B", 1);
graph.addNodes("E","G", 1);
graph.addNodes("G","E", 1);
graph.addNodes("G","A", 1);
graph.addNodes("D","A", 1);
graph.addNodes("D","F", 1);
graph.addNodes("F","B", 1);
graph.addNodes("F","C", 1);
graph.addNodes("C","F", 1);
graph.addNodes("C","H", 1);
graph.addNodes("H","C", 1);
graph.printAdjacencyList();
ArrayList<Vertex> bfs = graph.breadthFirstSearch(graph.getVertexByName("A"));
ArrayList<Vertex> dfs = graph.depthFirstSearch(graph.getVertexByName("A"));
System.out.print("BFS ");
printVertexList(bfs);
System.out.print("DFS ");
printVertexList(dfs);
System.out.println("Shortest distance between A and H is " + graph.djksraShortestPath("A", "H"));
}
public static void main(String [ ] args){
simpleGraph();
complicatedGraph();
}
The output:
Simple Graph
Vertex: A B/1.0 D/1.0 G/1.0
Vertex: B E/1.0 F/1.0
Vertex: D A/1.0 F/1.0
Vertex: G E/1.0 A/1.0
Vertex: E B/1.0 G/1.0
Vertex: F B/1.0 C/1.0
Vertex: C F/1.0 H/1.0
Vertex: H C/1.0
BFS A B D G E F C H
DFS A G E B F C H D
Shortest distance between A and H is 4.0
Complicated Graph
Vertex: A B/20.0 D/80.0 G/90.0
Vertex: B F/10.0
Vertex: D G/20.0 C/10.0
Vertex: G A/20.0
Vertex: F D/40.0 C/10.0
Vertex: E B/50.0 G/30.0
Vertex: C F/50.0 D/10.0 H/20.0
Vertex: H
BFS A B D G F C H
DFS A G D C H F B
Shortest distance between A and H is 60.0
Shortest distance between A and E is Infinity
Shortest distance between D and H is 30.0
Ariel's Dev Snippets 