2.1.3. Path Computation

Try these first

1. 1.

   What are the nodes and edges in the context of an airline network?

   Hint

   Think about what each part of the network represents.

2. 2.

   How can you simplify a graph without changing its meaning?

   Hint

   Consider which elements are essential for understanding the network.

3. 3.

   What does connectivity refer to in a graph?

   • Whether there is a direct flight
   • The existence of a path between nodes
   • The total number of edges

   Hint

   Think about what connectivity means in a travel scenario.

4. 4.

   True or False: A planar graph can have edges that cross.

   • True
   • False

   Hint

   Recall the definition of planar graphs.

5. 5.

   Given a flight graph with ten cities and specific flight connections, derive an algorithm to determine the shortest path considering both time and cost constraints for air travel.

   Hint

   Think about how prioritizing factors can change the evaluation order.

6. 6.

   If two cities are temporarily disconnected due to maintenance and other routes are still operational, modify your pathfinding algorithm to ensure complete reachability from any city.

   Hint

   Consider how you can dynamically change the graph while preserving its structure.