Work-Integrated Learning Programmes Division
Second Semester 2016-2017
EC-1 Lab Component
Course Title : Data Structures & Algorithms Design Due Date : 02/05/2017
Course No : SS ZG 519 Total : 10 marks
Given adirected, weighted graph in the format described below, your task is to nd the shortest distance between two
vertices A and B in the graph. If there are multiple shortest paths between A and B, you have to nd the path with
the least number of edges.
Input Format
The vertices are represented by numbers starting from one. The rst line will include two numbers N and M, the number
of vertices in the graph and the number of edges in the graph respectively. The following M lines will have three
numbers each, u, v, w which represents adirected edge between u and v with a weight w. The nal line will have the
values of A and B, the nodes between which you will have to nd the shortest path.
Output Format
Print two numbers separated by a space: C E, where C is the cost from A to B and E is the number of edges from A
to B. For unreachable nodes, print -1 -1, denoting no valid distance and no valid number of edges, i.e. C = -1 and
E = -1.
Example 1
Consider the following graph. It has ve vertices and ve edges. We have to nd the shortest part from vertex 1 to vertex
5. There are two shortest paths, based on the weight of the path, from vertex 1 to vertex 5: path 1,2,5 and path
1,3,4,5. But we want to nd the path with minimum number of edges. So we pick the path with total weight 3 and number
of edges 2.
Input for Example 1
5 5
1 2 1
1 3 1
2 5 2
3 4 1
4 5 1
1 5
Output for Example 1
3 2
Constraints
Consider the fact the input graph can be quite large. You should come up with e cient
code to avoid the timeout error. However, there is a limit on the number of vertices and
number of vertices as follows.
1 <= M <= 104
1 <= N <= 104
No comments:
Post a Comment