subject: design and analysis of algorithm

please read question completely and carefully donot copy answers from internet

do fast

Question 3 Given a directed, weighted, connected graph G (V, E) and two vertices u & v, find the shortest path between u & v that passes through a vertex e. [what it means, you have to find that if there is a shortest path from u to v that should pass through vertex e and this path should be the shortest of all available from u to v through e, if no path available from u to v through e then return -1] It is required to write function(s), in pseudo-code, that finds and returns shortest distance between vertices u & v that passes through another vertex e. If there is no such path, the function returns -1. All the three vertices u, v&e are in a weighted, directed, connected graph G (V, E), with positive weights. [You should write a generic solution for this problem, in-term of u, v and e vertices) Example: To give the basic understanding that how you have to think to produce your solution 1. The shortest distance path between vertices S & E that passes through vertex Dis 9 in the following graph. S-A-D-E (2+4 + 6) S-A-D-B-E (2 + 4 + 2 + 5) S-A-D-C-E (2 + 4 + 2 + 1) 2. The shortest distance path between vertices S & B that passes through vertex C in the following graph is not possible. Therefore, the function returns -1. As Sto B there is a path but it has no option to take any possible route through C Pseudo solution needed (first write your ides in points that how you will solve the example)