Find the cheapest path from a to b and its time complexity

Assignment Help Basic Computer Science

Reference no: EM131361643

In certain graph problems, vertices have can have weights instead of or in addition to the weights of edges. Let Cv be the cost of vertex v, and C(x,y) the cost of the edge (x, y). This problem is concerned with finding the cheapest path between vertices a and b in a graph G. The cost of a path is the sum of the costs of the edges and vertices encountered on the path.

(a) Suppose that each edge in the graph has a weight of zero (while non-edges have a cost of ∞). Assume that Cv = 1 for all vertices 1 ≤ v ≤ n (i.e. , all vertices have the same cost). Give an efficient algorithm to find the cheapest path from a to b and its time complexity.

(b) Now suppose that the vertex costs are not constant (but are all positive) and the edge costs remain as above. Give an efficient algorithm to find the cheapest path from a to b and its time complexity.

(c) Now suppose that both the edge and vertex costs are not constant (but are all positive). Give an efficient algorithm to find the cheapest path from a to b and its time complexity

Reference no: EM131361643

Questions Cloud

Regression equation-cancellations : For a regression equation, "cancellations" is my dependent variable and I want to know how many cancellations will be at 6pm since hour is my independent variable.

Read the following short story-young goodman brown : Read the following short story:"Young Goodman Brown."by Nathanial Hawthorne.Read the following psycoanalytic approach to that story: Nathaniel Hawthorne's "Young Goodman Brown": A Psychoanalytic Reading by Margaret Weld.

Conduct research on principles of managememt controlling : Conduct research on these 2 principles of managememt controlling and leading. You have been asked to give a presentation to a group of new managers in a health care setting.

Rank correlation coefficient for the aggressiveness scores : Using the table below, compute the spearman rank correlation coefficient for the aggressiveness scores. Does this suggest that both twins tend to be similar in degrees of aggressiveness?

Find the cheapest path from a to b and its time complexity : Now suppose that both the edge and vertex costs are not constant (but are all positive). Give an efficient algorithm to find the cheapest path from a to b and its time complexity

Medical facilitator : As a medical facilitator, you are asked to analyze data from the past years patient visits. As you analyze, you look at the median wait time before seen by a physician. Would the median be the best representation of the wait time, please explain?

Perform the indicated operation and simplify : Perform the indicated operation and simplify. Write your final answer in scientific nota- tion, rounded to two decimal places: (4.23 × 1023)50

Design and implement an algorithm for solving the subgraph : How does your program perform on such special cases of subgraph isomorphism as Hamiltonian cycle, clique, independent set, and graph isomorphism?

Solve the single-source longest path problem : Can we modify Dijkstra's algorithm to solve the single-source longest path problem by changing minimum to maximum? If so, then prove your algorithm correct. If not, then provide a counterexample.

User Account

All Pages