Question

What is the length of a longest simple path in the weighted graph in Figure 4 between \(a\)and \(z\)? Between \(c\) and \(z\)?

Short answer

The longest simple path between \(a\) and \(z\) is \(a,b,d,c,e,z\). The longest simple path between \(c\) and \(z\) is \(c,e,d,z\).

Step-by-step solution

Given data

The Graph is given as,

Concept used of Dijkstra’s algorithm

Dijkstra's algorithm allows us to find the longest path between any two vertices of a graph.

Find the longest path 

The longest path from \(atoz\)is obtained by considering the paths with maximum weights possible. This forces the edges \(c,e\) and \(c,z\) to be included in the longest path. The other edges are chosen as to have maximum possible weights in order to increase the total weight of the path. Thus, we obtain the longest path from \(a\) to \(z\) is the path \(a,b,d,c,e,z\). Next, we consider the choice of weights for the longest path between \(c\) and \(z\). We cannot accommodate both the edges \(c\),\(d\) and \(c,e\)(with maximum weights) as this would result in a loop. Consider the two possible paths \(c,e,d,z\) and \(c,d,e,z\) of lengths 18 and 13 to conclude that the longest path between \(c\) and \(z\) is \(c,e,d,z\).