Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class indivisualvertex implements Comparable<indivisualvertex> {
- int data; //data associated with the vertex
- double distanceFromSource; //will store the distances from the source vertex
- int previousVertexOnShortestPathFromSource;//will store the previous vertex on the path
- neighbours adjacentPointsList; // neighbouring vertices stored in a linked list
- //for sorting the vertices in the priority queue according to their distances from the source
- public int compareTo(indivisualvertex other) {
- if (this.equals(other)) {
- return 0;
- } else if (this.distanceFromSource > other.distanceFromSource) {
- return 1;
- } else {
- return -1;
- }
- }
- }
- private void relax(indivisualvertex indx) {
- //traverse the neighbouring edges
- for (neighbours nbr = indx.adjacentPointsList; nbr != null; nbr = nbr.next){
- //condition where a vertex is unvisited and also provides a shorter path
- if (visited[nbr.pointer_of_vertex] == false && vertices[nbr.pointer_of_vertex].distanceFromSource > vertices[nbr.from].distanceFromSource + nbr.weight) {
- pq.remove(vertices[nbr.pointer_of_vertex]);
- vertices[nbr.pointer_of_vertex].distanceFromSource = vertices[nbr.from].distanceFromSource + nbr.weight;
- vertices[nbr.pointer_of_vertex].previousVertexOnShortestPathFromSource = nbr.from;
- pq.add(vertices[nbr.pointer_of_vertex]);
- }
- }
- }
Add Comment
Please, Sign In to add comment