Dynamic Programming - Counting paths in a subway system

Question

I have a network of stations in a subway system. The number of stations, the number of tickets I can travel between stations with, and which stations are connected to each other are given in a text file as input to the program. Which stations are connected to each other are kept in a 2D boolean matrix. I have to find the number of paths from station 0 and back to 0 that uses all of the tickets.

Here is one of the examples:

In that example, there are 7 stations and 5 tickets. Starting and returning to 0, there are 6 paths:

0-1-2-3-4-0
0-1-5-3-4-0
0-1-6-3-4-0
0-4-3-6-1-0
0-4-3-5-1-0
0-4-3-2-1-0

I currently have a recursive solution to this that runs in O(N^k) (N represents the number of stations while k is the number of tickets), but I have to convert it to an iterative, dynamic programming solution in O(k*N^2) that works on any input.

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <vector>

using namespace std;


// We will represent our subway as a graph using
// an adjacency matrix to indicate which stations are
// adjacent to which other stations.
struct Subway {
  bool** connected;
  int nStations;

  Subway (int N);

private:
  // No copying allowed
  Subway (const Subway&) {}
  void operator= (const Subway&) {}
};


Subway::Subway(int N)
{
  nStations = N;
  connected = new bool*[N];
  for (int i = 0; i < N; ++i)
    {
      connected[i] = new bool[N];
      fill_n (connected[i], N, false);
    }
}

unsigned long long int callCounter = 0;
void report (int dest, int k)
{
  ++callCounter;
  // Uncomment the following statement if you want to get a feel 
  // for how many times the same subproblems get revisited
  // during the recursive solution.
  cerr << callCounter << ": (" << dest << "," << k << ")" << endl;
}


/**
 * Count the number of ways we can go from station 0 to station destination
 * traversing exactly nSteps edges.
 */
unsigned long long int tripCounter (const Subway& subway, int destination, int nSteps)
{
    report (destination, nSteps);
    if (nSteps == 1)
    {
        // Base case: We can do this in 1 step if destination is
        // directly connected to 0.
        if (subway.connected[0][destination]){
            return 1;
        }
        else{
            return 0;
        }
    }
    else
    {
        // General case: We can get to destinaiton in nSteps steps if
        // we can get to station S in (nSteps-1) steps and if S connects
        // to destination.
        unsigned long long int totalTrips = 0;
        for (int S = 0; S < subway.nStations; ++S)
        {
            if (subway.connected[S][destination])
            {
                // Recursive call
                totalTrips += tripCounter (subway, S, nSteps-1);
            }
        }
        return totalTrips;
    }
}

// Read the subway description and
// print the number of possible trips.
void solve (istream& input)
{
  int N, k;
  input >> N >> k;
  Subway subway(N);
  int station1, station2;
  while (input >> station1)
    {
      input >> station2;
      subway.connected[station1][station2] = true;
      subway.connected[station2][station1] = true;
    }
  cout << tripCounter(subway, 0, k) << endl;
  // For illustrative/debugging purposes
  cerr << "Recursive calls: " << callCounter << endl;
}




int main (int argc, char** argv)
{
  if (argc > 1) 
    {
      ifstream in (argv[1]);
      solve (in);
    }
  else
    {
      solve (cin);
    }
  return 0;
}

I'm not looking for a solution. I am currently out of ideas and hoping someone can point me in the right direction. Since I'm required to implement a bottom-up approach for this, how would I start with developing a dynamic programming table using the smallest sub-problems?

Answer 1

You should construct an array T that for each step T[i] tells "how many paths are there between 0 and i".

For 0 steps, this array is:

[1, 0, 0, ... 0]

Then, for each step, do:

T_new[i] = sum{0<=j<n}(T[j] if there is an edge (i, j))

After k of those steps, T[0] will be the answer.

Here's a simple Python implementation to illustrate:

def solve(G, k):
    n = len(G)

    T = [0]*n
    T[0] = 1

    for i in xrange(k):
        T_new = [
            sum(T[j] for j in xrange(n) if G[i][j]) 
            for i in xrange(n)
        ]
        T = T_new

    return T[0]

G = [
     [0, 1, 0, 0, 1, 0, 0],
     [1, 0, 1, 0, 0, 1, 1],
     [0, 1, 0, 1, 0, 0, 0],
     [0, 0, 1, 0, 1, 1, 1],
     [1, 0, 0, 1, 0, 0, 0],
     [0, 1, 0, 1, 0, 0, 0],
     [0, 1, 0, 1, 0, 0, 0]
]

print solve(G, 5) #6

Answer 2

Dynamic programming works by recursively storing the previous subproblem result. In your case the subproblems consist of finding the number of all paths that, given a number of tickets k, can reach a station.

In the base case you have 0 tickets and thus the only station you can reach is station 0 with no paths. To kickstart the algorithm we assume that the null path is also a valid path.

At this point I would recommend you to get a piece of paper and try it out yourself first. The recursion you need is something like

set base case (i.e. station 0 == 1 null path)    

for each ticket in [1;k]
  stations = get the stations which were reached at the previous step
  for each station in stations
    spread the number of paths they were reached with to the neighbors

return the number of paths for station 0 with k tickets

The complete DP algorithm, minimizing the number of changes needed to integrate it into your code, follows

/**
* Count the number of ways we can go from station 0 to station destination
* traversing exactly nSteps edges with dynamic programming. The algorithm
* runs in O(k*N^2) where k is the number of tickets and N the number of
* stations.
*/
unsigned int tripCounter(const Subway& subway, int destination, int nSteps)
{
  map<int, vector<int>> m;
  for (int i = 0; i < nSteps + 1; ++i)
    m[i].resize(subway.nStations, 0);

  m[0][0] = 1; // Base case

  for (int t = 1; t < m.size(); ++t) { // For each ticket

    vector<int> reachedStations;
    for (int s = 0; s < subway.nStations; ++s) { // For each station
      if (m[t-1][s] > 0)
        reachedStations.push_back(s); // Store if it was reached in the previous state
    }

    for (auto s : reachedStations) {
      // Find adjacent stations
      for (int adj = 0; adj < subway.nStations; ++adj) {
        if (s == adj)
          continue;
        if (subway.connected[s][adj])
          m[t][adj] += m[t-1][s];
      }
    }
  }
  return m[nSteps][0];
}

Complexity is as asked. Make sure you understand the code before using it.

As you will learn iterating over subproblems is a common pattern in dynamic programming algorithms.