const int INF = 1e9;

struct edge {
    int u, v, cost;
};

vector<edge> edges;
vector<int> dist(n, INF);
dist[source] = 0;

// Step 2: Relax all edges n - 1 times
for (int i = 0; i < n - 1; ++i) {
    for (edge e : edges) {
        if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.cost) {
            dist[e.v] = dist[e.u] + e.cost;
        }
    }
}

// Step 3: Check for negative weight cycles
bool hasNegativeCycle = false;
for (edge e : edges) {
    if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.cost) {
        hasNegativeCycle = true;
        break;
    }
}

Problem and Solution Explanation: Problem 423 - MPI Maelstrom

Problem Description:

The problem "MPI Maelstrom" (Problem 423) on Online Judge involves finding the shortest paths in a network represented as an adjacency matrix. The network describes connections between nodes, with edge weights representing communication costs. The goal is to determine the minimum cost for a message to be broadcast from a source node (node 1) to all other nodes in the network. Note that the input graph will not have negative weight cycles.

Solution Explanation:

This problem is a classic application of the single-source shortest path problem. Since the problem guarantees no negative weight cycles, Dijkstra's algorithm would typically be the go-to solution. However, since the document is about the Bellman-Ford algorithm, we can use it here.

Here's how Bellman-Ford can be applied to solve this problem:

Input Processing:

• Read the number of nodes, n, from the input.
• Create an adjacency matrix to represent the network. Initialize the matrix. The diagonal elements (cost from a node to itself) are 0. The input provides the upper triangle of the matrix. For entries where no direct connection is given, we can assume a large value (representing infinity) to indicate no direct path. We need to populate the lower triangle of the matrix by reflecting the values from the upper triangle since the graph is undirected.

Initialization:

• Create a distance array, dist, of size n. Initialize all elements to infinity (a large value) except dist[0] (distance from node 1 to itself), which is set to 0.

Bellman-Ford Algorithm:

• Iterate n - 1 times. In each iteration, iterate through all possible edges in the graph.
• For each edge (u, v) with weight w (cost from the adjacency matrix), relax the edge: If dist[u] + w < dist[v], update dist[v] to dist[u] + w.

Output:

• After the iterations, the dist array will contain the shortest distances from node 1 to all other nodes. Find the maximum value in the dist array, as the problem asks for the minimum cost to reach all nodes. Print this maximum value.

Why Bellman-Ford Works Here:

• Single Source Shortest Path: We need to find the shortest path from a single source (node 1) to all other nodes.
• No Negative Weight Cycles: The problem statement guarantees no negative weight cycles, which is a requirement for Bellman-Ford to find the correct shortest paths.
• Correctness: After n - 1 iterations, Bellman-Ford guarantees finding the shortest paths in a graph without negative cycles.

Key Points:

• The problem uses 1-based indexing, but the solution and code use 0-based indexing.
• The algorithm efficiently handles the graph represented as an adjacency matrix.
• The final answer is the maximum of all shortest paths from the source to all other nodes.

Code Solution (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int main() {
    int n;
    cin >> n;

    // Create adjacency matrix
    vector<vector<int>> adj_matrix(n, vector<int>(n, INF)); 
    for (int i = 0; i < n; ++i) {
       adj_matrix[i][i] = 0; // Distance from node to itself is 0
  }

    // Read upper triangle of the matrix
    for (int i = 1; i < n; ++i) {
       for (int j = 0; j < i; ++j) {
          string cost_str;
          cin >> cost_str;
          if (cost_str != "x") {
              int cost = stoi(cost_str);
              adj_matrix[i][j] = cost;
              adj_matrix[j][i] = cost; // Copy to lower triangle
           }
       }
   }

    // Initialize distances
    vector<int> dist(n, INF);
    dist[0] = 0; // Distance from node 1 (0-indexed) to itself is 0

    // Bellman-Ford
    for (int i = 0; i < n - 1; ++i) {
        for (int u = 0; u < n; ++u) {
            for (int v = 0; v < n; ++v) {
                if (adj_matrix[u][v] != INF && dist[u] != INF && dist[u] + adj_matrix[u][v] < dist[v]) {
                    dist[v] = dist[u] + adj_matrix[u][v];
                }
            }
        }
    }

    // Find the maximum distance
    int max_dist = 0;
    for (int i = 0; i < n; ++i) {
        max_dist = max(max_dist, dist[i]);
    }

    cout << max_dist << endl;

    return 0;
}
    

Explanation of the Code:

• Include Headers: Includes the necessary iostream, vector, and algorithm headers.
• Constants and Namespaces: Defines INF and uses the standard namespace.
• Main Function:
  • Reads the number of nodes, n.
  • Creates an adjacency matrix adj_matrix of size n x n and initializes it.
  • Reads the input for the upper triangle of the adjacency matrix and populates the lower triangle.
  • Initializes the distance vector dist.
  • Implements the Bellman-Ford algorithm.
  • Finds the maximum distance in the dist vector.
  • Prints the maximum distance.