Updated: Sep 17
Advanced Computer Networks(CEG-7450-01) - Packet Routing: Part I. Least Cost Path Routing (Java Solution) Packets in a network need to traverse a minimum-cost route. Design an algorithm to determine which nodes the packets will definitely visit if least cost path(s) are used. Note there may be multiple least cost paths.
Unlike previous labs, this lab reads input from the standard input. DO NOT include any package statement in your program.
The first input line contains two integers n (1<= n <= 10^5) and m (1<=m<=2x10^5): the number of nodes and the number of links. The nodes are numbered 1,2,…,n. Node 1 is the source, and node n is the destination.
After this first line, there are m lines describing the links. Each line has three integers a, b, and c: there is a link from node a to node b with cost c. All links are directional. That is, a, b, c indicates that there is a link from a to b only, with a cost of c. In addition, 1 <=a, b<=n, 1<=c <=10^9.
You may assume that there is a route from the source to the destination.
Unlike previous labs, the output is to the standard output.
First print an integer k: the number of nodes that are certainly in the route. After this, print the k nodes sorted in increasing order.
SAMPLE INPUT 1:
1 2 3
1 3 4
2 3 1
2 4 5
3 4 1
4 5 8
SAMPLE OUTPUT 1:
1 3 4 5
For Assignment Help Please WhatsApp at:
+91-995 3141 035
Solution Includes: AI writing Detection and Plagiarism report with 100% Accuracy.