26.1.2. Exploration of Graphs

Try these first

1. 1.

   What is a weighted graph?

   Hint

   Think about how costs could represent real-world scenarios like distance or price.

2. 2.

   Can you explain what Dijkstra's algorithm does?

   Hint

   Consider how you’d navigate from one point to many others while minimizing cost.

3. 3.

   What does a weighted graph have that an unweighted graph doesn't?

   • No edges
   • Associated costs with edges
   • More vertices

   Hint

   Think about how costs represent additional information.

4. 4.

   True or False: Dijkstra's algorithm can be used for graphs with negative edge weights.

   • True
   • False

   Hint

   Recall the properties required for Dijkstra's to work effectively.

5. 5.

   Create a weighted graph based on a map of your city. Label the edge weights based on travel time. After that, calculate the shortest path using Dijkstra's algorithm and provide your results.

   Hint

   Pay close attention to the edge weights during calculations to ensure accuracy.

6. 6.

   Given a matrix representation of a weighted graph with several vertices, identify negative cycles and discuss the suitability of Dijkstra’s algorithm for this scenario.

   Hint

   Review properties of negative cycles and their implications on graphs.