Explanation Algorithm used: Dijkstra’s Algorithm. Consider that G is a weighted graph in which there are more than one vertices and all weights are positive. This algorithm is used to determine the distance and a shortest path from vertex S to every other vertex in the weighted graph G . P is the set of vertices with permanent labels. The predecessor of A is a vertex in P used to label A . The weight of the edge on vertices U and V is denoted by W ( U , V ) , and if there is no edge on U and V , it can be written that W ( U , V ) = ∞ . Algorithm. Step 1 (label) Assign S the label 0, and let S have no predecessor. Set P = { S } . Step 2 (Label vertices) Assign to each vertex V not in P the (perhaps temporary) label W ( S , V ) , and let V have the (perhaps temporary) predecessor S . Step 3 (enlarge P and revise labels) Repeat Step 3.1 (make another label permanent) Include in P a vertex U having the smallest label of the vertices not in P . (If there is more than one such vertex, arbitrarily choose any one of them.) Step 3.2 (revise temporary labels) For each vertex X not in P that is adjacent to U , replace the label on X with the smaller of the old label on X and the sum of the label on U and W ( U , X ) . If the label on X was changed, let U be the new (perhaps temporary) predecessor of X . Until P contain every vertex of G . Step 4 (Find distance and shortest paths) The label on a vertex Y is its distance from S . If the label on Y is infinite, then there is not path, and hence no shortest path, from S to Y . Otherwise, a shortest path from S to Y is formed by using in reverse order the vertices Y , the predecessor of Y , the predecessor of the predecessor of Y , and so forth, until S is reached. Description: Consider the given figure. Step 1: Begin with setting P = { S } and assign label 0 to S . Step 2: Assign the label W ( S , V ) and the predecessor S to every other vertex V. Therefore, W ( S , V ) = ∞ . This is in case there is no edge which joins S and V. Step 3: The vertex which is not in P with the smallest label is C . Therefore, include C in P

5th Edition

ISBN: 9780134689562

Author: Dossey, John A.

Publisher: Pearson,

See similar textbooks

Videos

Question

Chapter 4, Problem 19SE

To determine

The distance from S to all other vertices and the shortest path from S to A and S to B in the given graph.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 4, Problem 18SE

Chapter 4, Problem 20SE

Students have asked these similar questions

3. We'd like to know the first time when the population reaches 7000 people. First, graph the function from part (a) on your calculator or Desmos. In the same window, graph the line y = 7000. Notice that you will need to adjust your window so that you can see values as big as 7000! Investigate the intersection of the two graphs. (This video shows you how to find the intersection on your calculator, or in Desmos just hover the cursor over the point.) At what value t> 0 does the line intersect with your exponential function? Round your answer to two decimal places. (You don't need to show work for this part.) (2 points)

Suppose the planet of Tattooine currently has a population of 6500 people and an annual growth rate of 0.35%. Use this information for all the problems below. 1. Find an exponential function f(t) that gives the population of Tattooine t years from now. (3 points)

A house was valued at $95,000 in the year 1988. The value appreciated to $170,000 by the year 2007. A) If the value is growing exponentially, what was the annual growth rate between 1988 and 2007? Round the growth rate to 4 decimal places. r = B) What is the correct answer to part A written in percentage form? r = 3 %.

Chapter 4 Solutions

Discrete Mathematics

Ch. 4.1 - In Exercises 1–4, list the set of edges and set of...Ch. 4.1 - Prob. 2E Ch. 4.1 - Prob. 3E Ch. 4.1 - Prob. 4E Ch. 4.1 - Prob. 5E Ch. 4.1 - In Exercises 5–8, draw a diagram representing the...Ch. 4.1 - Prob. 7E Ch. 4.1 - In Exercises 5–8, draw a diagram representing the...Ch. 4.1 - Prob. 9E Ch. 4.1 - In Exercises 9–14, determine whether a graph is...

Ch. 4.1 - Prob. 11E Ch. 4.1 - Prob. 12E Ch. 4.1 - Prob. 13E Ch. 4.1 - Prob. 14E Ch. 4.1 - Prob. 15E Ch. 4.1 - Prob. 16E Ch. 4.1 - Prob. 17E Ch. 4.1 - Draw the graph with ν = {1, 2, … , 10} as its set...Ch. 4.1 - Prob. 19E Ch. 4.1 - Prob. 20E Ch. 4.1 - Prob. 21E Ch. 4.1 - Show that there are an even number of vertices...Ch. 4.1 - Prob. 23E Ch. 4.1 - Prob. 24E Ch. 4.1 - Prob. 25E Ch. 4.1 - Prob. 26E Ch. 4.1 - Prob. 27E Ch. 4.1 - In Exercises 26–29, find the adjacency matrix and...Ch. 4.1 - Prob. 29E Ch. 4.1 - In Exercises 30 and 31, construct the graph for...Ch. 4.1 - Prob. 31E Ch. 4.1 - In Exercises 32 and 33, construct the graph for...Ch. 4.1 - Prob. 33E Ch. 4.1 - Prob. 34E Ch. 4.1 - Prob. 35E Ch. 4.1 - In Exercises 35-37, can each matrix be an...Ch. 4.1 - Prob. 37E Ch. 4.1 - Prob. 38E Ch. 4.1 - Prob. 39E Ch. 4.1 - Prob. 40E Ch. 4.1 - Prob. 41E Ch. 4.1 - Are the pairs of graphs in (a), (b), and (c)...Ch. 4.1 - Are the pairs of graphs in (a), (b), and (c)...Ch. 4.1 - Draw all the non isomorphic graphs with three...Ch. 4.1 - Prob. 45E Ch. 4.1 - Draw all the nonisomorphic graphs with five...Ch. 4.1 - Prob. 47E Ch. 4.1 - Prob. 48E Ch. 4.1 - Prob. 49E Ch. 4.1 - Suppose a graph has n vertices, each with degree...Ch. 4.1 - Prob. 51E Ch. 4.1 - Prob. 52E Ch. 4.1 - Suppose Mr. and Mrs. Lewis attended a bridge party...Ch. 4.1 - Prove that if a graph has at least two vertices,...Ch. 4.2 - In Exercises 1–4, determine whether the multigraph...Ch. 4.2 - Prob. 2E Ch. 4.2 - Prob. 3E Ch. 4.2 - Prob. 4E Ch. 4.2 - Prob. 5E Ch. 4.2 - Prob. 6E Ch. 4.2 - Prob. 7E Ch. 4.2 - Prob. 8E Ch. 4.2 - Prob. 9E Ch. 4.2 - In Exercises 9 and 10, perform the following...Ch. 4.2 - Prob. 11E Ch. 4.2 - Prob. 12E Ch. 4.2 - Prob. 13E Ch. 4.2 - Prob. 14E Ch. 4.2 - Prob. 15E Ch. 4.2 - Prob. 16E Ch. 4.2 - Prob. 17E Ch. 4.2 - In Exercises 18–23, determine whether the...Ch. 4.2 - Prob. 19E Ch. 4.2 - In Exercises 18–23, determine whether the...Ch. 4.2 - Prob. 21E Ch. 4.2 - In Exercises 18–23, determine whether the...Ch. 4.2 - Prob. 23E Ch. 4.2 - In Exercises 24–29, determine whether the...Ch. 4.2 - Prob. 25E Ch. 4.2 - Prob. 26E Ch. 4.2 - Prob. 27E Ch. 4.2 - Prob. 28E Ch. 4.2 - Prob. 29E Ch. 4.2 - Prob. 30E Ch. 4.2 - Prob. 31E Ch. 4.2 - Prob. 32E Ch. 4.2 - Prob. 33E Ch. 4.2 - Prob. 34E Ch. 4.2 - Prob. 35E Ch. 4.2 - Prob. 36E Ch. 4.2 - Prob. 37E Ch. 4.2 - An old childhood game asks children to trace a...Ch. 4.2 - Prob. 39E Ch. 4.2 - In 1859, Sir William Rowan Hamilton, a famous...Ch. 4.2 - Give examples of connected graphs satisfying each...Ch. 4.2 - Prob. 42E Ch. 4.2 - Prob. 43E Ch. 4.2 - Prob. 44E Ch. 4.2 - Prob. 45E Ch. 4.2 - Prob. 46E Ch. 4.2 - Prob. 47E Ch. 4.2 - Prob. 48E Ch. 4.2 - Prob. 49E Ch. 4.2 - Are the following two graphs isomorphic? Justify...Ch. 4.2 - Prob. 51E Ch. 4.2 - A bipartite graph is a graph in which the vertices...Ch. 4.2 - Prob. 53E Ch. 4.2 - Prob. 54E Ch. 4.2 - Prob. 55E Ch. 4.2 - Prob. 56E Ch. 4.2 - Prob. 57E Ch. 4.2 - Prob. 58E Ch. 4.2 - Prob. 59E Ch. 4.2 - Prob. 60E Ch. 4.2 - Prob. 61E Ch. 4.2 - Prob. 62E Ch. 4.2 - Prob. 64E Ch. 4.2 - Prob. 65E Ch. 4.3 - In Exercises 1–4, use the breadth-first search...Ch. 4.3 - In Exercises 1–4, use the breadth-first search...Ch. 4.3 - Prob. 3E Ch. 4.3 - In Exercises 1–4, use the breadth-first search...Ch. 4.3 - In Exercises 5–8, determine the distance from S to...Ch. 4.3 - In Exercises 5–8, determine the distance from S to...Ch. 4.3 - Prob. 7E Ch. 4.3 - Prob. 8E Ch. 4.3 - Prob. 9E Ch. 4.3 - Prob. 10E Ch. 4.3 - Prob. 11E Ch. 4.3 - Prob. 12E Ch. 4.3 - Prob. 13E Ch. 4.3 - Prob. 14E Ch. 4.3 - For the following graph, determine the number of...Ch. 4.3 - Prob. 16E Ch. 4.3 - Prob. 17E Ch. 4.3 - Prob. 18E Ch. 4.3 - Prob. 19E Ch. 4.3 - Prob. 20E Ch. 4.3 - Prob. 21E Ch. 4.3 - Prob. 22E Ch. 4.3 - Prob. 23E Ch. 4.4 - In Exercises 1–8, find the chromatic number of the...Ch. 4.4 - Prob. 2E Ch. 4.4 - Prob. 3E Ch. 4.4 - Prob. 4E Ch. 4.4 - Prob. 5E Ch. 4.4 - Prob. 6E Ch. 4.4 - Prob. 7E Ch. 4.4 - Prob. 8E Ch. 4.4 - Prob. 9E Ch. 4.4 - Prob. 10E Ch. 4.4 - Prob. 11E Ch. 4.4 - It might be supposed that if a graph has a large...Ch. 4.4 - Prob. 13E Ch. 4.4 - Prob. 15E Ch. 4.4 - Prob. 16E Ch. 4.4 - Prob. 17E Ch. 4.4 - Prob. 18E Ch. 4.4 - Prob. 19E Ch. 4.4 - Suppose is a graph with three vertices. How many...Ch. 4.4 - Prob. 21E Ch. 4.4 - Prob. 22E Ch. 4.4 - Prob. 23E Ch. 4.4 - Prob. 24E Ch. 4.4 - Prob. 25E Ch. 4.4 - Prob. 26E Ch. 4.4 - Prob. 27E Ch. 4.4 - Prob. 28E Ch. 4.4 - Prob. 29E Ch. 4.4 - Prob. 30E Ch. 4.4 - Prob. 31E Ch. 4.4 - Prob. 32E Ch. 4.4 - Prob. 33E Ch. 4.4 - Show that it is possible to assign one of the...Ch. 4.4 - Prob. 35E Ch. 4.4 - Prove Theorem 4.9 by mathematical induction on the...Ch. 4.4 - Suppose that each vertex of a graph is such that...Ch. 4.5 - In Exercises 1–4, list the vertices and directed...Ch. 4.5 - Prob. 2E Ch. 4.5 - Prob. 3E Ch. 4.5 - Prob. 4E Ch. 4.5 - Prob. 5E Ch. 4.5 - Prob. 6E Ch. 4.5 - Prob. 7E Ch. 4.5 - Prob. 8E Ch. 4.5 - Prob. 9E Ch. 4.5 - Prob. 10E Ch. 4.5 - Prob. 11E Ch. 4.5 - Prob. 12E Ch. 4.5 - Prob. 13E Ch. 4.5 - Prob. 14E Ch. 4.5 - Prob. 15E Ch. 4.5 - Prob. 16E Ch. 4.5 - Prob. 17E Ch. 4.5 - Prob. 18E Ch. 4.5 - Prob. 19E Ch. 4.5 - Prob. 20E Ch. 4.5 - Prob. 21E Ch. 4.5 - Prob. 22E Ch. 4.5 - Prob. 23E Ch. 4.5 - Prob. 24E Ch. 4.5 - Prob. 25E Ch. 4.5 - Prob. 26E Ch. 4.5 - Prob. 27E Ch. 4.5 - Prob. 28E Ch. 4.5 - Prob. 29E Ch. 4.5 - Prob. 30E Ch. 4.5 - Prob. 31E Ch. 4.5 - Prob. 32E Ch. 4.5 - Prob. 33E Ch. 4.5 - Prob. 34E Ch. 4.5 - Prob. 35E Ch. 4.5 - Prob. 36E Ch. 4.5 - Prob. 37E Ch. 4.5 - Prob. 39E Ch. 4.5 - Prob. 40E Ch. 4.5 - Prob. 41E Ch. 4.5 - Prob. 42E Ch. 4.5 - Prob. 43E Ch. 4.5 - Prob. 44E Ch. 4.5 - Prob. 45E Ch. 4.5 - Prob. 46E Ch. 4.5 - Prob. 47E Ch. 4.5 - Prob. 48E Ch. 4.5 - Prob. 49E Ch. 4.5 - Prob. 51E Ch. 4.5 - Prob. 52E Ch. 4.5 - Prob. 53E Ch. 4.5 - Prob. 54E Ch. 4.5 - Prob. 55E Ch. 4.5 - Prob. 56E Ch. 4.5 - Prob. 57E Ch. 4.5 - Prob. 58E Ch. 4.5 - Prob. 59E Ch. 4.5 - Prob. 60E Ch. 4.5 - Write a breadth-first search algorithm for...Ch. 4.5 - Prob. 62E Ch. 4.5 - Prob. 63E Ch. 4.5 - Prob. 64E Ch. 4.5 - Prob. 65E Ch. 4.5 - Prob. 66E Ch. 4.5 - Prob. 67E Ch. 4.5 - In Exercises 67–70, determine the distance from S...Ch. 4.5 - In Exercises 67–70, determine the distance from S...Ch. 4.5 - Prob. 70E Ch. 4.5 - Prob. 71E Ch. 4.5 - Prob. 72E Ch. 4.5 - Prob. 73E Ch. 4.5 - Prob. 74E Ch. 4.5 - Prob. 75E Ch. 4.5 - Determine whether the following pairs of directed...Ch. 4.5 - Determine whether the following pairs of directed...Ch. 4.5 - Prob. 78E Ch. 4.5 - Prob. 79E Ch. 4.5 - Prob. 80E Ch. 4.5 - Prob. 82E Ch. 4.5 - Prob. 83E Ch. 4.5 - Prob. 84E Ch. 4 - Prob. 1SE Ch. 4 - Prob. 2SE Ch. 4 - Prob. 3SE Ch. 4 - Prob. 4SE Ch. 4 - Prob. 5SE Ch. 4 - Prob. 6SE Ch. 4 - Prob. 7SE Ch. 4 - Prob. 8SE Ch. 4 - Prob. 9SE Ch. 4 - Prob. 10SE Ch. 4 - Prob. 11SE Ch. 4 - Prob. 12SE Ch. 4 - Prob. 13SE Ch. 4 - Prob. 14SE Ch. 4 - Is the property “is connected” a graph isomorphism...Ch. 4 - Prob. 16SE Ch. 4 - Prob. 17SE Ch. 4 - Prob. 18SE Ch. 4 - Prob. 19SE Ch. 4 - Prob. 20SE Ch. 4 - Prob. 21SE Ch. 4 - Prob. 22SE Ch. 4 - Prob. 23SE Ch. 4 - Prob. 24SE Ch. 4 - Prob. 25SE Ch. 4 - Prob. 26SE Ch. 4 - Prob. 28SE Ch. 4 - Prob. 29SE Ch. 4 - Prob. 30SE Ch. 4 - Prob. 31SE Ch. 4 - Prob. 32SE Ch. 4 - Prob. 34SE Ch. 4 - Prob. 35SE Ch. 4 - Prob. 36SE Ch. 4 - Prob. 37SE Ch. 4 - Prob. 38SE Ch. 4 - Prob. 39SE Ch. 4 - Prob. 40SE Ch. 4 - Prob. 6CP Ch. 4 - Prob. 9CP Ch. 4 - Prob. 14CP

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.