top of page

Advanced Computer Networks(CEG-7450-01) - Packet Routing - Part I. Least Cost Path Routing(Java)

Updated: Sep 17, 2023

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.


INPUT FORMAT:

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.


OUTPUT FORMAT:


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:

5 6

1 2 3

1 3 4

2 3 1

2 4 5

3 4 1

4 5 8


SAMPLE OUTPUT 1:

4

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.



26 views0 comments

Comentários


bottom of page