Reference no: EM131146323
1. We have discussed Dijkstra's algorithm in class for computing the shortest paths from any source node to all other nodes in a network. The first step is to codify the network information, i.e., how do we represent the link costs? One way is to use a matrix representation. If the link costs have been expressed as a matrix C, then the (i, j)th element of the matrix gives the cost of the link between i and j (obviously, if i = j, Cif = 0, for all i). For example, the cost matrix for the network shown in Fig. 1 is (first row/column is for node A, second row/column is for node B, etc.):
You can assume that the user would not make any error in entering the link cost matrix (i.e., the matrix would be symmetric, non-negative, and al elements along the leading diagonal will be 0). That is, your code does not need to check for potential errors in the link cost matrix.
Write a function computeDijkstra(sourceID,C)' which takes as inputs the source node ID and the link cost matrix and returns the final best cost vector and the final predecessor vector.
For example, referring to slide-38 of Chapter-5 notes, your out¬put arguments should be [0,2,3,1,2,4] and [A, A, E, A, D, El or [1,1,5,1,4,5] if you label each node by a numeric, i.e., [A, B, C, D, E] -4 [1,2,3,4,5].
The pseudocode is available on slide-36 of Chapter-5 notes.
If you cannot implement the predecessor vector, just try to return the final cost vector. You can earn up to 50 points if you do so correctly.
You cannot use built in functions which directly compute the shortest path tree or implement Dijkstra's algorithm.
Here's a MATLAB tip. Suppose x = [2, 3, 1, 4, 5]. Executing (a,b) = min(x) returns a=1 and b=3. The parameter b therefore returns the position in x where the minimum is found.
Figure 1: Network for Problem 1.
NOTE: You should email me your codes with instructions on how to rim than.
Find the number of cycles after which the motion ceases
: the number of cycles after which the motion ceases. Assume the mass of the pendulum is m and the coefficient of friction between the shaft and the bearing of the pendulum is µ.
|
Discuss some of goods or services that could be highlighted
: Discuss some of the goods or services that could be highlighted in a marketing campaign that involves a concierge practice of medicine. What advantages do you think a concierge practice of medicine might contribute to the hospital's offerings of ..
|
How to spot phantom inventory
: There are many ways that a company can manipulate inventory information reported on their balance sheet in order to make the business appear financially healthy. How to Spot Phantom Inventory?
|
Why is important for scientists to study whole solar system
: Why is it important for scientists to study the whole solar system? Choose a planned space mission or a space mission from the past 10 years and describe its purpose. What do you think we have learned or will potentially learn from this mission? G..
|
Compute shortest path tree or implement dijkstras algorithm
: Write a function compute Dijkstra(sourceID,C)' which takes as inputs the source node ID and the link cost matrix and returns the final best cost vector and the final predecessor vector - You cannot use built in functions which directly compute the ..
|
Find the kinetic coefficient of friction
: A metal block, placed on a rough surface, is attached to a spring and is given an initial displacement of 10 cm from its equilibrium position. It is found that the natural time period of motion is 1.0 s and that the amplitude reduces by 0.5 cm in ..
|
What are the public perceptions of the hazard
: What types of adverse health effects might be caused by the problem? How quickly and for what duration might the problem be experienced?
|
Determine the time taken to complete the 10 cycles
: is made to vibrate on a rough surface. If the friction force f = 20 N is and the amplitude of the mass is observed to decrease by 50 mm in 10 cycles, determine the time taken to complete the 10 cycles.
|
What are three new types of merchandising accounts
: What is the difference between a service and a merchandising business? Provide an example of each. What are three new types of merchandising accounts?
|