Register

Cormen Edition 3 Exercise 1.1 Question 4 (Page No. 11)

323 views

1 Answer

2 votes
2 votes

They are similar in the sense that both traverse a graph and try to find out the shortest path with minimum cost (sum of the weights).

They are different because the shortest-path problem finds a path between two points such that the sum of the weights is minimized. At the same time, the traveling-salesman problem finds a way to cover all the points (the start and end point is the same) such that the sum of the weights is minimized. Also, the shortest-path problem is P complex, and the traveling salesman is NP-complete.

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
akash.dinkar12 asked Apr 4, 2019
475 views
Cormen Edition 3 Exercise 11.4 Question 1 (Page No. 277)
Consider inserting the keys $10, 22, 31, 4,15,28,17,88,59$ into a hash table of length $m =11$ using open addressing with the auxiliary hash function $h'(k) =k$ ... double hashing with $h_1(k) =k$ and $h_2(k)$ $=$ $1$+$($k$ $mod$ $(m-1)$)$.
Consider inserting the keys $10, 22, 31, 4,15,28,17,88,59$ into a hash table of length $m =11$ using open addressing with the auxiliary hash function $h’(k) =k$. Illust...
User Avatar
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Apr 4, 2019
393 views
Cormen Edition 3 Exercise 11.4 Question 5 (Page No. 277)
Consider an open-address hash table with a load factor $\alpha$ Find the nonzero value $\alpha$ for which the expected number of probes in an unsuccessful search equals twice the expected number of probes in a successful search.
Consider an open-address hash table with a load factor $\alpha$ Find the nonzero value $\alpha$ for which the expected number of probes in an unsuccessful search equals t...
User Avatar
Link Copied!