Melanie is a second$-$year computer science student currently studying at Griffith School of ICT. One day,

Melanie$$s father came to her and told her that he wants to travel from Southport to Brisbane CBD and asks

Melanie to recommend exactly $-$shortest loopless paths for some reason. Luckily, Melanie is undertaking

the $2801$ICT: Computing Algorithms$$ course. Though, Melanie knows both Dijkstra$$s algorithm and

Bellman Ford$$s algorithm very well as these two algorithms have been taught already in the class, she is

not exactly sure how to solve this $-$shortest loopless paths problem for the Queensland road network

graph. This is an interesting problem and it could be solved by the following requirement. Melanie$$s father

is happy if and only if the first recommended path is the shortest path between Southport to Brisbane

CBD and the rest of the $$ paths are approximated shortest paths as these paths are his backup

paths.

Problem Description

The shortest path problem is about finding a path between $2$ vertices in a graph such that the total sum of

the edges weights is minimum. This problem could be solved easily using $($BFS$)$ if all edge weights were

$1,$ but here weights can take any value. There are TWO popular algorithms in the literature for computing

the shortest paths from the source vertex to all other vertices in a graph: $($i$)$ Dijkstra's Algorithm; and $($ii$)$

Bellman Ford$$s Algorithm. The Bellman Ford$$s algorithm exploits the idea that a shortest path contains at

most $1$ edges, and a shortest path cannot have a cycle. The Bellman Ford$$s algorithm works for graphs

with negative weight cycle$($s$).$ The time complexity of Dijkstra's Algorithm with min$-$priority queue is

$(+$ log $).$ On the other hand, the time complexity of Bellman Ford algorithm is relatively high

$(.),$ in case $=2$

$,(3).$ Both Dijkstra's and Bellman Ford$$s algorithms unable to solve the this $-$

shortest loopless paths $($KSP$)$ problem. There exist many works in the literature to solve KSP problem.

Some useful references are given at the end of this document.

In this problem, you are given $2$ integers $(,),$ is the number of vertices, $$ is the number of edges.

You will also be given $,,$ where $$ and $$ represents an edge from a vertex $$ to a vertex $$ and

$$ respresents the weight of that edge. Finally, you will be given two vertices $$ and $,$ where $$ denotes the

source vertex $($Southport$)$ and $$ denotes the destination vertex $($Brisbane CBD$)$ and the value of $.$

For each input file, print the length of the $-$shortest loopless paths separated by commas and these paths

must include the shortest path between $$ and $$ and the rest of the $$ paths are approximated

shortest paths.

Sample Input: Consider the following directed graph as an example.

$69$

C D $3$

C E $2$

D F $4$

E D $1$

E F $2$

E G $3$

F G $2$

F H $1$

G H $2$

C H $3$

Sample Output: $5,7,8$

The $3$ shortest paths from source C to destination H are as follows:

P$1=$ C$->$E$->$F$->$H$,$ Cost $($P$1)=5$

P$2=$ C$->$E$->$G$->$H$,$ Cost $($P$2)=7$

P$3=$ C$->$D$->$F$->$H$,$ Cost $($P$3)=8$

Sample Results for Java Implementation $($Yen Algorithm$)$

Input $($k$=?)$ Output CPU Time $($millisecs$)$

$21038\mathrm{.}57,1042\mathrm{.}381286$

$31038\mathrm{.}57,1042\mathrm{.}38,1043\mathrm{.}022007$

$51038\mathrm{.}57,1042\mathrm{.}38,1043\mathrm{.}02,1043\mathrm{.}29,1044\mathrm{.}057767$

$71038\mathrm{.}57,1042\mathrm{.}38,1043\mathrm{.}02,1043\mathrm{.}29,1044\mathrm{.}05,1044\mathrm{.}12,1044\mathrm{.}6310897$

$101038\mathrm{.}57,1042\mathrm{.}38,1043\mathrm{.}02,1043\mathrm{.}29,1044\mathrm{.}05,1044\mathrm{.}12,1044\mathrm{.}63,$

$1044\mathrm{.}90,1045\mathrm{.}73,1045\mathrm{.}97$