Prim's algorithm: pick-up and drop-off locations for packages

• member 428835
In summary, Prim's algorithm is a popular method for finding the most efficient route for picking up and dropping off packages. It works by selecting the shortest path between locations and gradually adding more locations until all packages have been delivered. This algorithm is widely used in logistics and transportation industries to optimize delivery routes and reduce costs. It also takes into account factors such as traffic and distance, making it a reliable and effective solution for package delivery.
member 428835
This question statement is below, but I can't find out what it's even asking. Any help?

[chegg link redacted by the Mentors after the content was posted below. Please avoid posting low-quality chegg links]

Last edited by a moderator:
1. Drop-off Centers
An e-commerce company, WhatDoYouWant, wants to contract with local businesses to use their stores as pick-up and drop-off locations for their packages. To reduce expenses, they want to ensure that their drop centers are a minimum distance apart from each other.
A city has many potential drop centers (pdcs) to choose from, represented as nodes on a weighted, undirected graph. The edges on this graph denote roads that connect pdcs, with weights representing the lengths of the roads.
Determine how many unique subsets of these companies can be contracted that would satisfy that requirement.

Baluncore said:
1. Drop-off Centers
An e-commerce company, WhatDoYouWant, wants to contract with local businesses to use their stores as pick-up and drop-off locations for their packages. To reduce expenses, they want to ensure that their drop centers are a minimum distance apart from each other.
A city has many potential drop centers (pdcs) to choose from, represented as nodes on a weighted, undirected graph. The edges on this graph denote roads that connect pdcs, with weights representing the lengths of the roads.
Determine how many unique subsets of these companies can be contracted that would satisfy that requirement.
What is the requirement?

joshmccraney said:
What is the requirement?
"they want to ensure that their drop centers are a minimum distance apart from each other."

Mark44 said:
"they want to ensure that their drop centers are a minimum distance apart from each other."
So like Prim's algorithm?

joshmccraney said:
So like Prim's algorithm?
I don't know anything about Prim's algorithm. You asked "What is that requirement?"
My answer was based on what Baluncore wrote, which I presume came directly from the problem you linked to.

Mark44 said:
I don't know anything about Prim's algorithm. You asked "What is that requirement?"
My answer was based on what Baluncore wrote, which I presume came directly from the problem you linked to.
So for the first triangle shown, would the answer be 5, since all circles are connected with total length 5?

Does such a poorly posed question deserve such attention ?
Maybe it is just click bait, designed to get you to sign up.

jim mcnamara, pbuk and member 428835
The minimum distance is provided as a parameter to the function you must write as your solution. In the example shown the minimum distance is 4. As the distance between nodes 1 and 2 in the diagram for this example is 3 then any subset that includes both nodes 1 and 2 violates the minimum distance constraint. Note that the example is not expressed correctly as there is no graph_weight argument provided; can you work out what it should be given the weights in the diagram?

Last edited:
Baluncore said:
Does such a poorly posed question deserve such attention ?
Maybe it is just click bait, designed to get you to sign up.
Chegg seems to be featuring a lot in threads here recently, and also in general internet search results: they must have been pumping it on many levels and obviously plan to make a lot of money. Some of their questions and examples clearly need debugging: do we want to help them do this?

Last edited:
pbuk said:
Chegg seems to be featuring a lot in threads here recently, and also in general internet search results: they must have been pumping it on many levels and obviously plan to make a lot of money. Some of their questions and examples clearly need debugging: do we want to help them do this?
Well, it's weird because this was literally a coding interview question I had. I obviously didn't take the time to post this until after the interview was complete (not a cheater and honestly no time), but I had no clue what the question was asking. Consequently I didn't even attempt the question. But after the interview I started googling to see what on Earth was being asked. Still don't fully understand, but I'm fine with that.

Maybe the interviewer found the question on Chegg.com
Maybe they wanted to see how you would react when intimidated by such a poorly posed problem.

member 428835 and berkeman
Baluncore said:
Maybe the interviewer found the question on Chegg.com
Maybe they wanted to see how you would react when intimidated by such a poorly posed problem.
LOLOL it was generated by a computer, and it didn't have the lines and line weights. Also, it used the acronym "pdcs" without definition, along with several other errors. Also, one multiple choice answer about flow charts wasn't available. I even coded it afterwords and nada. The whole process was very weird.

1. What is Prim's algorithm and how does it work?

Prim's algorithm is a greedy algorithm used to find the minimum spanning tree in a weighted undirected graph. It starts with a single vertex and gradually adds the closest vertex until all vertices are included in the tree. It works by selecting the next edge that has the lowest weight and is connected to the current tree.

2. What are the applications of Prim's algorithm?

Prim's algorithm is commonly used in network design, such as finding the most efficient route for package delivery. It is also used in data compression, image segmentation, and clustering.

3. How does Prim's algorithm handle edge weights?

Prim's algorithm assumes that all edge weights are positive. If there are negative edge weights, the algorithm may not find the minimum spanning tree. In such cases, other algorithms like Dijkstra's algorithm can be used.

4. Can Prim's algorithm handle disconnected graphs?

No, Prim's algorithm can only be applied to connected graphs. If the graph is disconnected, the algorithm will only find a minimum spanning tree for one of the connected components.

5. How does Prim's algorithm handle cycles in a graph?

Prim's algorithm avoids creating cycles by only selecting edges that connect to vertices that are not already in the tree. If a cycle is encountered, the algorithm will skip that edge and choose the next closest vertex. This ensures that the resulting tree is acyclic.

• Programming and Computer Science
Replies
6
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
914
• Programming and Computer Science
Replies
8
Views
2K
• Programming and Computer Science
Replies
1
Views
2K
• Programming and Computer Science
Replies
29
Views
3K
• Programming and Computer Science
Replies
4
Views
5K
• Electrical Engineering
Replies
14
Views
876
• Computing and Technology
Replies
3
Views
2K