In line 21, we can change the priority of a vertex v by updating its distance to alt directly. If we use an original priority queue, we need to search the whole priority queue in order to locate the priority queue node that stores vertex v. This takes time complexity O(|V]). You are going to design and explain how the data structures, distance array and priority queue, are changed such that we can locate the node in the priority queue quickly i.e. O(1).
In line 21, we can change the priority of a vertex v by updating its distance to alt directly. If we use an original priority queue, we need to search the whole priority queue in order to locate the priority queue node that stores vertex v. This takes time complexity O(|V]). You are going to design and explain how the data structures, distance array and priority queue, are changed such that we can locate the node in the priority queue quickly i.e. O(1).
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
a and b
![11. In the original Dijkstra's algorithm,
function Dijkstra(Graph, source):
dist[source] + 0
// Initialization
2
3
4
create vertex priority queue Q
5
for each vertex v in Graph:
if v # source
7
8
dist[v] + INFINITY
// Unknown dist from source to
V
9
prev[v] + UNDEFINED
// Predecessor of v
10
11
Q. add_with_priority(v, dist[v])
12
13
while Q is not empty:
u - Q. extract_min()
for each neighbor v of u: // only v that are still in Q
// The main loop
// Remove and return best vertex
14
15
16
alt +
if alt < dist[v]
dist[v] + alt
prev[v] + u
Q.decrease_priority(v, alt)
17
dist[u] + length(u, v)
18
19
20
21
22
23
return dist, prev
Source: Wikipedia](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F52af42bc-e2b8-439e-b96f-7491e88243ba%2Fb549cc9e-4a55-4a1b-88e1-da8a2fdb12e7%2Fr0gez93_processed.png&w=3840&q=75)
Transcribed Image Text:11. In the original Dijkstra's algorithm,
function Dijkstra(Graph, source):
dist[source] + 0
// Initialization
2
3
4
create vertex priority queue Q
5
for each vertex v in Graph:
if v # source
7
8
dist[v] + INFINITY
// Unknown dist from source to
V
9
prev[v] + UNDEFINED
// Predecessor of v
10
11
Q. add_with_priority(v, dist[v])
12
13
while Q is not empty:
u - Q. extract_min()
for each neighbor v of u: // only v that are still in Q
// The main loop
// Remove and return best vertex
14
15
16
alt +
if alt < dist[v]
dist[v] + alt
prev[v] + u
Q.decrease_priority(v, alt)
17
dist[u] + length(u, v)
18
19
20
21
22
23
return dist, prev
Source: Wikipedia
![In line 21, we can change the priority of a vertex v by updating its distance to alt directly.
If we use an original priority queue, we need to search the whole priority queue in order
to locate the priority queue node that stores vertex v. This takes time complexity O(|V]).
You are going to design and explain how the data structures, distance array and priority
queue, are changed such that we can locate the node in the priority queue quickly i.e.
O(1).
Are there any changes in the data structure of the distance array?
Are there any changes in the data structure of the node in the priority queue?
c. When the distance of vertex v is updated to alt, how can we locate the node in the
priority queue storing vertex v in O(1)?
d. In the priority queue, let node P be the parent of node Lchild and node Rchild. If the
priority of Lchild is changed and you need to update the priority queue by swapping
the content of node P and node Lchild, are there extra things you need to update?](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F52af42bc-e2b8-439e-b96f-7491e88243ba%2Fb549cc9e-4a55-4a1b-88e1-da8a2fdb12e7%2Fodp15bj_processed.png&w=3840&q=75)
Transcribed Image Text:In line 21, we can change the priority of a vertex v by updating its distance to alt directly.
If we use an original priority queue, we need to search the whole priority queue in order
to locate the priority queue node that stores vertex v. This takes time complexity O(|V]).
You are going to design and explain how the data structures, distance array and priority
queue, are changed such that we can locate the node in the priority queue quickly i.e.
O(1).
Are there any changes in the data structure of the distance array?
Are there any changes in the data structure of the node in the priority queue?
c. When the distance of vertex v is updated to alt, how can we locate the node in the
priority queue storing vertex v in O(1)?
d. In the priority queue, let node P be the parent of node Lchild and node Rchild. If the
priority of Lchild is changed and you need to update the priority queue by swapping
the content of node P and node Lchild, are there extra things you need to update?
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY