Chapter 7: Graph Algorithms II

Activity 15: Greedy Robot

We can solve this activity using the exact algorithm from Exercise 33, Implementing the Bellman-Ford Algorithm (Part II). The potential pitfalls here are related to correctly interpreting the required task and representing the graph within the context of the problem you are actually trying to solve. Let's get started:

1. The first step will be identical to the exercise. We will include the same headers and define an Edge struct and an UNKNOWN constant:

   #include <iostream>
   #include <vector>
   #include <climits>
   using namespace std;
   struct Edge
   {
           int start;
           int end;   
           int weight;
           Edge(int s, int e, int w) : start(s), end(e), weight(w) {}
   };
   const int UNKNOWN = INT_MAX;
   vector<Edge*> edges;

2. In...