26.1.7.1. Describing the Burning Process

Try these first

1. 1.

   What is a weighted graph?

   Hint

   Think about what costs might represent in an application.

2. 2.

   What does edge cost represent?

   Hint

   Consider what expense could be related to transport.

3. 3.

   What does a weighted graph include?

   • Only edges
   • Edges with costs
   • Vertices only

   Hint

   Think about graphs used in transportation.

4. 4.

   True or False: A shortest path always has the fewest edges.

   • True
   • False

   Hint

   Reflect on the burning analogy.

5. 5.

   Consider a graph with vertices A, B, C, and D connected by edges with the following weights: A-B: 4, A-C: 2, C-B: 5, B-D: 1. Calculate the shortest path from A to D using Dijkstra's algorithm.

   Hint

   Keep track of the lowest costs as you move through unvisited vertices.

6. 6.

   You have a weighted graph where some edges are negative. What will happen when applying Dijkstra's Algorithm, and what alternative would you consider?

   Hint

   Review the properties of the algorithms for different contexts.