Due to the Corona Virus or COVID-19 the entire world is experiencing situations that we have never seen before. The Internet, TV and other news sources are full of reports. Some of them have good and valuable information while most are just opinions which have no scientific background. We should seek information from reliable sources and when possible check our findings against multiple reliable sources and use common sense, which as we know is not the most common of the senses.
Yesterday evening I started this post and wrote about two pages regarding 
COVID-19. Today started reading it and decided to delete them with the exception of the first sentence. There is already too much information out there. Please stay home. If you need to go out for groceries, please keep social distance. Healthcare facilities are already taking care of more patients that they were designed for.
OK, enough about COVID-19 and let’s get to the subject of this post.
I started the associated code on one of my Windows 10 machines. When done I push it to GitHub. Typically I start by creating a repo at GitHub and then updating it when done. I was working on different code for different projects. When I was ready to start writing this post I noticed I was on a different GitHub repo. I had to get back to the repository that holds the code for this post.
C:\Users\johnc\workspace0\GraphMultipleCosts>git remote -v origin https://github.com/JohnCanessa/MinimumPenaltyPath.git (fetch) origin https://github.com/JohnCanessa/MinimumPenaltyPath.git (push) C:\Users\johnc\workspace0\GraphMultipleCosts>git remote set-url origin https://github.com/JohnCanessa/GraphMultipleCosts.git C:\Users\johnc\workspace0\GraphMultipleCosts>git remote -v origin https://github.com/JohnCanessa/GraphMultipleCosts.git (fetch) origin https://github.com/JohnCanessa/GraphMultipleCosts.git (push) C:\Users\johnc\workspace0\GraphMultipleCosts>
The idea behind this post was to experiment and try different implementations of Dijkstra’s shortest distance algorithm. I experimented with different data structures and considered different problems. The resulting code is what I ended up with.
5 7 1 2 6 1 4 1 2 4 2 2 5 2 2 3 5 4 5 1 5 3 5 1 3 shortestPath <<< path: 1 -> 4 -> 5 -> 3 shortestPath <<< cost: 7 5 7 1 2 6 1 4 1 2 4 2 2 5 2 2 3 5 4 5 1 5 3 5 4 3 shortestPath <<< path: 4 -> 5 -> 3 shortestPath <<< cost: 6 5 7 1 2 6 1 4 1 2 4 2 2 5 2 2 3 5 4 5 1 5 3 5 5 1 shortestPath <<< path: 5 -> 4 -> 1 shortestPath <<< cost: 2 3 4 1 2 1 1 2 1000 2 3 3 1 3 100 1 3 shortestPath <<< path: 1 -> 2 -> 3 shortestPath <<< cost: 4 5 5 1 5 8 1 2 1 2 3 2 3 4 3 4 5 4 1 5 7 shortestPath <<< path: 1 -> 5 shortestPath <<< cost: 8 8 9 1 2 1 1 3 2 2 4 1 3 4 2 4 5 10 5 6 1 5 7 2 6 8 1 7 8 2 1 8 shortestPath <<< path: 1 -> 2 -> 4 -> 5 -> 6 -> 8 shortestPath <<< cost: 14 4 5 1 2 1 1 2 2 2 3 10 3 4 2 3 4 1 1 4 shortestPath <<< path: 1 -> 2 -> 3 -> 4 shortestPath <<< cost: 12
The format of the test cases is as follows:
The first line contains the number of vertices followed by the number of edges. The following lines contain three integers. The first is the source node, the 
second the destination node and the third value the cost (or distance). The last line contains the source and destination vertices for which we need to generate a path and compute their cost (or total distance).
If you take the time and draw some of the diagrams associated with the test cases, you will find that they are different from each other in at least one way. You will find that some graphs contain multiple edges between the same nodes. Not all possible graph cases are solved by using the smallest cost (or distance).
After processing the input data, the path and the cost is displayed.
/**
* Test scaffolding.
*
* @throws FileNotFoundException
*/
public static void main(String[] args) throws FileNotFoundException {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read number of nodes and edges ****
String[] nm = sc.nextLine().trim().split(" ");
int m = Integer.parseInt(nm[1]);
// **** graph edges (includes cost) ****
int[][] edges = new int[m][3];
// **** loop reading vertices and associated cost ****
for (int i = 0; i < m; i++) {
String[] edgeCost = sc.nextLine().trim().split(" ");
edges[i][0] = Integer.parseInt(edgeCost[0]);
edges[i][1] = Integer.parseInt(edgeCost[1]);
edges[i][2] = Integer.parseInt(edgeCost[2]);
}
// **** read the start and end vertices ****
String[] ab = sc.nextLine().trim().split(" ");
int A = Integer.parseInt(ab[0]);
int B = Integer.parseInt(ab[1]);
// **** find and display path and cost ****
shortestPath(edges, A, B);
// **** close scanner ****
sc.close();
}
The test scaffolding is quite simple. We open a scanner to read in the data.
We then read the first line and only extract the number of edges. With that we create an array of edges and proceed to loop reading one line at a time.
The source and destination vertices followed by the cost are read and parsed.
When we have read all the edges, we read the source and destination vertices. Our challenge is to determine the path between these two vertices and the cost (or distance) to get from one to the other.
As usual, we close the scanner.
/**
* Node for graph class.
* Supports multiple edges with different costs between vertices.
*/
class Node {
// **** members ****
public int v;
HashMap<Integer, ArrayList<Integer>> adj;
/**
* constructor
*/
public Node(int v) {
this.v = v;
this.adj = new HashMap<Integer, ArrayList<Integer>>();
}
/**
* Return a string with the representation of this node.
*/
@Override
public String toString() {
// **** ****
StringBuilder sb = new StringBuilder();
// **** ****
sb.append(" v: " + this.v);
sb.append(" adj: ");
adj.entrySet().stream().forEach(e -> sb.append("u: " + e.getKey() + " c: " + e.getValue() + " "));
// **** return string ****
return sb.toString();
}
}
We define the class Node (perhaps we should have named it Vertex) to hold the name of a vertex and a hash map to hold the edges. Since our implementation should support multiple edges from any vertex, we use the key of the hash map to name adjacent vertices and an array list to keep track of all possible costs. For example, vertex 1 may have two adjacent nodes, 2 and 3. There might be one or more costs to travel from vertex 1 to 2. The same holds true if we wish to move from vertex 1 to vertex 3.
At first this might sound irrational, but such conditions do exist. Think of two cities and 2 or more roads / highways / freeways connecting them which you could choose from to get from one city to another. The distance of a road will not change during the course of a day, but traffic conditions will. The edge would not represent a distance but the cost (probably in minutes) to travel from one city to another at the specified time of the day. At 02:00 AM we could travel between cities in 15 minutes, while during morning rush hour, that same path might take 53 minutes to cover.
The Node class has a constructor and a toString method to get a string representation in case needed. I used it when implementing the code. There are a few test cases and it is simpler and faster to display information to the console that single step through the code.
/**
* Graph class.
*/
class Graph {
// **** graph representation ****
HashMap<Integer, Node> graph = null;
/**
* Constructor
*/
public Graph() {
this.graph = new HashMap<Integer, Node>();
}
/**
* Get the number of vertices in the graph.
*/
public int getSize() {
return this.graph.size();
}
/**
* Add node to graph.
*/
public Node addNode(int v) {
// **** lookup an existing node ****
if (graph.containsKey(v))
return graph.get(v);
// **** create a new node ****
Node node = new Node(v);
// **** add the new node into the graph ****
graph.put(v, node);
// **** return the new node ****
return node;
}
/**
* Returns a string representing the graph.
*/
@Override
public String toString() {
// **** ****
StringBuilder sb = new StringBuilder();
// **** ****
Iterator<Entry<Integer, Node>> it = this.graph.entrySet().iterator();
while (it.hasNext()) {
Entry<Integer, Node> e = it.next();
sb.append(e.getValue().toString());
}
// **** return string representation ****
return sb.toString();
}
/**
* Get an existing node form the graph.
*/
public Node getNode(int v) {
return graph.get(v);
}
/**
* Add v to graph if not present.
* Add u to graph if not present.
* Add adjacent vertex u to v with specified cost c.
* Add adjacent vertex v to u with specified cost c.
*/
public Node addVerticesAndEdge(int v, int u, int c) {
// **** get the v node ****
Node vn = getNode(v);
// **** check if we need to create the v node ****
if (vn == null) {
vn = addNode(v);
}
// **** get the u node ****
Node un = getNode(u);
// **** check if we need to create the u node ****
if (un == null) {
un = addNode(u);
}
// **** get the specified adjacent u vertex from vertex v ****
ArrayList<Integer> alUV = vn.adj.get(u);
// **** add adjacent vertex u with cost c ****
if (alUV == null) {
ArrayList<Integer> al = new ArrayList<Integer>();
al.add(c);
vn.adj.put(u, al);
}
// **** add cost c to adjacent vertex u ****
else {
alUV.add(c);
}
// **** get the specified adjacent v vertex from u ****
ArrayList<Integer> alVu = un.adj.get(v);
// **** add adjacent u with c ****
if (alVu == null) {
ArrayList<Integer> al = new ArrayList<Integer>();
al.add(c);
un.adj.put(v, al);
}
// **** return v node ****
return vn;
}
}
The Graph class is used to represent the graph. The hash map holds the vertex name (actually number) as the key and a node as the value. We could have simplified it further by condensing the vertex in the Node with the vertex in the Graph. I will leave that for further experimentation and optimization. If you feel inclined to get that done, please update the GitHub repo.
In the Graph class we have a constructor. We follow it by a method to get the size (number of vertices) of the graph. The addNode method is used to add a single node into the graph. As we will shortly find out, we typically add two nodes and their associated edge to the graph. More important, we are using bidirectional edges. That means we can get from vertex u to v as well as from v to u.
The toString method is used for debugging purposes. The getNode method returns the associated node based on the vertex name.
The addVerticesAnd Edge method is used to specify the vertices and the connecting edge. We first check that the u and v nodes exist. Then we add the edges from u to v and v to u. Note that we use the array list to keep the values for the cost of all edges.
/**
*
*/
public class Solution {
// **** set of unvisited vertices ****
static HashSet<Integer> unVisited = new HashSet<Integer>();
/**
* Select the unvisited vertex with the SMALLEST known distance from the start vertex.
*/
static int smallestCostVertex(int[] vertex, int[] sda, int[] pv) {
// **** looking for smallest value ****
int scv = Integer.MAX_VALUE;
// **** select the vertex with the shortest distance to vertex: a ****
for (int i = 1; i < sda.length; i++) {
// **** skip visited vertices ****
if (!unVisited.contains(i)) {
continue;
}
// **** check this vertex ****
if (sda[i] < scv)
scv = vertex[i];
}
// **** return smallest cost vertex ****
return scv;
}
/**
* Find the shortest paths from vertex: a to every other vertex in the specified
* graph.
*/
static void shortestPathFrom(Graph g, int a, int[] vertex, int[] sda, int[] pv, int[] vc) {
// **** set the distance from the start vertex: a to vertex: a ****
sda[a] = 0;
// **** loop while all vertices have not been visited ****
do {
// **** 1. visit the unvisited vertex (with the SMALLEST known distance) from the start vertex ****
int v = smallestCostVertex(vertex, sda, pv);
// **** check if no more vertices are available ****
if (v == Integer.MAX_VALUE) {
return;
}
// **** ****
Node node = g.getNode(v);
// **** 2. from the current vertex v, examine its unvisited neighbors u ****
for (Integer u : node.adj.keySet()) {
// **** check if we have already visited this vertex ****
if (!unVisited.contains(u))
continue;
// **** get the list of costs associatesd with vertex u ****
ArrayList<Integer> al = node.adj.get(u);
// **** for this edge u, compute and update the cost to a (if needed) ****
for (Integer c : al) {
// **** 3. calculate the cost ****
int cost = sda[v] + c;
// **** ****
if (cost < sda[u]) {
// **** 4. update cost from u to a ****
sda[u] = cost;
// **** 5. update the previous vertex (cost has been updated) ****
pv[u] = v;
// **** 6. update the cost to this vertex in the table ****
vc[u] = c;
}
}
}
// **** 7. remove this vertex from the unvisited list ****
unVisited.remove(v);
} while (unVisited.size() != 0);
}
/**
* Get a stack with the path from vertex b to vertex a (is implicit).
*/
static Stack<Integer> getPathBA(int[] vertex, int[] sda, int[] pv, int a, int b) {
// **** vertex stack ****
Stack<Integer> stackV = new Stack<Integer>();
// **** push last vertex ****
stackV.push(b);
// **** loop pushing costs ****
do {
// **** push vertex ****
stackV.push(pv[b]);
// **** set next vertex ****
b = pv[b];
} while (stackV.peek() != vertex[a]);
// **** return stack with vertices in the path ****
return stackV;
}
/**
* Return the sum of the costs from a to b.
*/
static int getCostBA(Stack<Integer> stack, int[] vc) {
// **** for starters ****
int cost = 0;
// **** traverse the stack ****
for (int i = stack.size() - 1; i > 0; i--) {
// **** ****
int u = stack.elementAt(i - 1);
// **** add the cost from vn to u ****
cost += vc[u];
}
// **** return the sum of the costs ****
return cost;
}
/**
* Display auxiliary table contents side by side.
*/
static void displayTables(int[] vertex, int[] sda, int[] pv, int[] vc) {
// **** display header ****
System.out.println("vertex\tsda\tpv\tvc");
// **** loop displaying table contents side by side ****
for (int i = 1; i < vertex.length; i++) {
System.out.printf("%d\t%d\t%d\t%d\n", vertex[i], sda[i], pv[i], vc[i]);
}
}
/**
* Compute and display the path and cost for the shortest path between two vertices.
*/
static void shortestPath(int[][] edges, int a, int b) {
// **** declare the graph ****
Graph g = new Graph();
// **** add vertices and costs to graph ****
for (int i = 0; i < edges.length; i++) {
g.addVerticesAndEdge(edges[i][0], edges[i][1], edges[i][2]);
}
// **** array (table) holding all vertices in the graph ****
int[] vertex = new int[g.getSize() + 1];
// **** array (table) holding the shortest distance from v ****
int[] sda = new int[g.getSize() + 1];
// **** array (table) holding previous vertex ****
int[] pv = new int[g.getSize() + 1];
// **** array (table) holding the cost to this vertex ****
int[] vc = new int[g.getSize() + 1];
// **** initialize data structures ****
for (int i = 0; i < g.getSize() + 1; i++) {
// **** ****
vertex[i] = i;
// **** fill in shortest distance from a ****
sda[i] = Integer.MAX_VALUE;
// **** populate unvisited vertices ****
if (i != 0)
unVisited.add(i);
}
// **** find shortest path in the graph from vertex: a to every other vertex ****
shortestPathFrom(g, a, vertex, sda, pv, vc);
// **** get a stack with the path from a to b ****
Stack<Integer> stack = getPathBA(vertex, sda, pv, a, b);
// **** display path between vertices ****
System.out.print("shortestPath <<< path: "); for (int i = stack.size() - 1; i >= 0; i--) {
System.out.print(stack.elementAt(i));
if (i > 0)
System.out.print(" -> ");
}
System.out.println();
// **** compute cost from A to B ****
int cost = getCostBA(stack, vc);
// **** display cost ****
System.out.println("shortestPath <<< cost: " + cost);
}
}
We use a hash set to keep track of vertices that have not been visited yet. This will become clear when we see the rest of the methods.
The smallestCostVertex returns the unvisited vertex with the smallest cost in the graph. This is used by the main algorithm by Dijkstra.
The shortestPathFrom method implements the core algorithm for the determining the distance between a vertex and the rest of them. Once we populate a set of tables, we can extract the distance we need to get a path and associated cost between vertices.
The algorithm is split into seven different tasks. I have numbered them in the order they appear. Note that the purpose of this method is to populate a set of tables with specific information. The vertex table holds an array with all the vertices in the graph. The sda table holds an array with the smallest cost (or shortest distance) from the specified vertex to vertex A. The pv array holds the name of the previous vertex. Finally, the vc array holds the cost (or distance) used to compute the smallest cost (or distance). This was done because there can be multiple edges between the same two vertices.
The getPathBA method is used to return in a stack the vertices between A and B with the minimum cost (or distance). Note that since each edge is bidirectional, the distance between A and B is the same as between B and A. If we use directed edges the path between the same set of nodes may be different.
The getCostBA method returns the cost (or distance) between the vertices A and B. Such information is encoded in the stack passed to it as an argument.
The displayTables method is used to display the contents of the auxiliary tables side by side. Looking at them this way makes it easier follow what is happening with the shortest distance algorithm.
The shortest Path method declares and populates the graph with the edges information we obtain in the main method, initializes the auxiliary tables, computes the shortest path, and get a stack representation of the path holding the vertices. It then displays the path from vertices A to B. The cost (or distance) is computed and displayed.
You should be able to use and modify this code to solve most minimum cost (shortest distance) graph problems using Dijkstra’s shortest path algorithm. Keep in mind that you could also perform a breath first traversal from vertex A to vertex B and get the same answer. We will explore such approach in a future post.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
One last thing, thanks to all 534 subscribers to my blog and please be safe!!!
John
Twitter: @john_canessa