Test: Dynamic Programming - 2 - Software Development MCQ

Which data structure is typically used to implement the Bellman–Ford algorithm efficiently?

The Bellman–Ford algorithm can handle graphs with:

What will be the output of the following code?
#include <iostream>
using namespace std;

#define INF 99999

int main() {
   int graph[4][4] = { {0, 3, INF, 5},
                       {2, 0, INF, 4},
                       {INF, 1, 0, INF},
                       {INF, INF, 2, 0} };

   for (int k = 0; k < 4; k++) {
       for (int i = 0; i < 4; i++) {
           for (int j = 0; j < 4; j++) {
               if (graph[i][j] > graph[i][k] + graph[k][j]) {
                   graph[i][j] = graph[i][k] + graph[k][j];
               }
           }
       }
   }

   cout << graph[1][3];

   return 0;
}

What will be the output of the following code?
#include <iostream>
using namespace std;

#define INF 99999

int main() {
   int graph[4][4] = { {0, INF, -2, INF},
                       {4, 0, 3, INF},
                       {INF, INF, 0, 2},
                       {INF, -1, INF, 0} };

   for (int k = 0; k < 4; k++) {
       for (int i = 0; i < 4; i++) {
           for (int j = 0; j < 4; j++) {
               if (graph[i][j] > graph[i][k] + graph[k][j]) {
                   graph[i][j] = graph[i][k] + graph[k][j];
               }
           }
       }
   }

   cout << graph[3][2];

   return 0;
}

What will be the output of the following code?
#include <iostream>
using namespace std;

#define INF 99999

int main() {
   int graph[4][4] = { {0, 3, 6, 15},
                       {INF, 0, -2, INF},
                       {INF, INF, 0, 2},
                       {1, INF, INF, 0} };

   for (int k = 0; k < 4; k++) {
       for (int i = 0; i < 4; i++) {
           for (int j = 0; j < 4; j++) {
               if (graph[i][j] > graph[i][k] + graph[k][j]) {
                   graph[i][j] = graph[i][k] + graph[k][j];
               }
           }
       }
   }

   cout << graph[0][3];

   return 0;
}

What will be the output of the following code?
#include <iostream>
using namespace std;

#define INF 99999

int main() {
   int graph[4][4] = { {0, 3, INF, 10},
                       {INF, 0, INF, 4},
                       {1, INF, 0, INF},
                       {INF, INF, 2, 0} };

   for (int k = 0; k < 4; k++) {
       for (int i = 0; i < 4; i++) {
           for (int j = 0; j < 4; j++) {
               if (graph[i][j] > graph[i][k] + graph[k][j]) {
                   graph[i][j] = graph[i][k] + graph[k][j];
               }
           }
       }
   }

   cout << graph[2][3];

   return 0;
}

What will be the output of the following code?
#include <iostream>
using namespace std;

#define INF 99999

int main() {
   int graph[4][4] = { {0, INF, INF, 10},
                       {4, 0, INF, INF},
                       {1, INF, 0, INF},
                       {INF, 5, 2, 0} };

   for (int k = 0; k < 4; k++) {
       for (int i = 0; i < 4; i++) {
           for (int j = 0; j < 4; j++) {
               if (graph[i][j] > graph[i][k] + graph[k][j]) {
                   graph[i][j] = graph[i][k] + graph[k][j];
               }
           }
       }
   }

   cout << graph[3][1];

   return 0;
}

Which algorithm can be used to find the shortest path in a directed acyclic graph (DAG)?

Which of the following statements is true regarding the Bellman–Ford algorithm?

Which algorithm can be used to find the shortest path between all pairs of vertices in a directed graph?

The Floyd Warshall algorithm has a time complexity of:

Which technique is used to solve problems in a multi-stage graph using dynamic programming?