in ancient country, there was a king that wanted to break up his kingdom so that
ID: 3833295 • Letter: I
Question
in ancient country, there was a king that wanted to break up his kingdom so that he could have his knights govern regions within his realm. However he knew that his knights would fight over their boundaries were in their various regions. He thought it might be a good idea to break up the regions based on the road system and city population. His goal was to balance the region's population so each knights would be in charge of approximately the same number of serfs and peasants. In addition, he would destroy any connectioning roads between regions so that the knights couldn't raid each other's regions. Of course, the king should be able to get to each region from the royal palace. The king wasn't sure how to go about dividing his country into regions. which ADT and algorithm would you use to help the king solve his problem? Outline your approach and how you would set up the problem to be solved. No pseudo code. in ancient country, there was a king that wanted to break up his kingdom so that he could have his knights govern regions within his realm. However he knew that his knights would fight over their boundaries were in their various regions. He thought it might be a good idea to break up the regions based on the road system and city population. His goal was to balance the region's population so each knights would be in charge of approximately the same number of serfs and peasants. In addition, he would destroy any connectioning roads between regions so that the knights couldn't raid each other's regions. Of course, the king should be able to get to each region from the royal palace. The king wasn't sure how to go about dividing his country into regions. which ADT and algorithm would you use to help the king solve his problem? Outline your approach and how you would set up the problem to be solved. No pseudo code.Explanation / Answer
Dijkstra's Shortest Path Algorithm is used for this problem.
Set a flag in all vertices to "UNSEEN"
Pick a starting vertex and mark it as "IN TREE" Mark all vertices adjacent to the start vertex as "FRINGE" Loop while there are vertices in the graph not marked as "IN TREE" Find the vertex in the fringe at a minimum distance from the start vertex. Add that vertex to the tree and mark it as "IN TREE" For each vertex adjacent to this vertex Set the state of the adjacent vertex to "FRINGE"Calculate its' distance from the starting vertex
Set the shortest distance to each node in the fringe end loop Return Shortest Distance.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.