Work Examples

Dijkstra's Shortest Path Algorithm

The following method was created to find the shortest path of a graph (stored in an adjacency list) using Dijkstra’s shortest path algorithm given a start vertex

		

public void Dijkstra(Vertex start) {



		HashMap predecessor = new HashMap(); //creates a hash map of predecessor vertices

		VertexCompareByDistance compare = new VertexCompareByDistance(); //uses a custom class to compare vertices by their distance

		PriorityQueue PQ = new PriorityQueue(compare); //creates a priority queue to store unvisited vertices in order of their distance



		

        //sets all vertices (except start vertex) to infinity (max integer value) and the start vertex to 0. additionally adds all vertices to the priority queue

		for (Vertex v:listOfVertices) {

			v.setDistance(Integer.MAX_VALUE);

			if (v == start) {

				start.setDistance(0);

			}

			PQ.add(v);

		}



        //while the priority queue is not exmpty

		while (!PQ.isEmpty()) {

			Vertex u = PQ.remove(); //remove the first element of priority queue

			for (Vertex v:getAdjacentVertices(u)) { //loops through all adjacent vertices of u

				if (PQ.contains(v)) { //if the priority queue contains the current vertex adjacenty to u

					int alt = u.getDistance() + getEdgeWeight(u,v); //create a temp variable and add the distance of u to the edge weight between u and v

					if (alt < v.getDistance()) { //if temp variable is less than distance of vertex v

						PQ.remove(v); //remove v from priority queue

						v.setDistance(alt); // set distance of v to temp variable

						PQ.add(v); //add v to priority queue (this time with new distance)

						predecessor.put(v, u); //add u to predecessor list with key v

					}

				}

			}

		}



}