26.1.1. Introduction to Weighted Graphs

Try these first

1. 1.

   What is a weighted graph?

   Hint

   Think about graphs with costs like distances or prices.

2. 2.

   What function assigns weights to edges in a graph?

   Hint

   What do we call the function that gives meaning to edge costs?

3. 3.

   What is a weighted graph?

   • A graph with no edges
   • A graph with edges having costs
   • A graph with only one vertex

   Hint

   Think about graphs that are used in real-life situations.

4. 4.

   True or False: BFS can always find the shortest path in a weighted graph.

   • True
   • False

   Hint

   Recall the limitations of BFS with regards to edge weights.

5. 5.

   Model a simple graph with at least 5 vertices and varying edge weights, and apply Dijkstra’s algorithm. What would the shortest paths from a source vertex look like?

   Hint

   Sketch the graph out and label the weights before starting the algorithm.

6. 6.

   Design a scenario where you compare single-source shortest paths to all pairs shortest paths in a real-world context. Discuss implications in decision-making.

   Hint

   Think about how each situation might change based on the approach taken.