#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <omp.h>
#include <limits.h>
#define INF INT_MAX
// Function to read the graph from a file
void readGraph(const char *filename, int *numNodes, int ***adjMatrix) {
FILE
*file
= fopen(filename
, "r"); if (file == NULL) {
fprintf(stderr
, "Error: Cannot open file %s\n", filename
); }
// Allocate memory for adjacency matrix
*adjMatrix
= (int **)malloc(*numNodes
* sizeof(int *)); for (int i = 0; i < *numNodes; i++) {
(*adjMatrix
)[i
] = (int *)malloc(*numNodes
* sizeof(int)); for (int j = 0; j < *numNodes; j++) {
fscanf(file
, "%d", &(*adjMatrix
)[i
][j
]); if ((*adjMatrix)[i][j] == 0 && i != j)
(*adjMatrix)[i][j] = INF; // Set unreachable edges to INF
}
}
}
// Function to compute Kth shortest path using Floyd-Warshall algorithm
void kthShortestPath(int numNodes, int **adjMatrix, int source, int dest, int k) {
int *dist
= (int *)malloc(numNodes
* numNodes
* sizeof(int)); int i, j, l;
// Initialize distance matrix
for (i = 0; i < numNodes; i++) {
for (j = 0; j < numNodes; j++) {
dist[i*numNodes + j] = adjMatrix[i][j];
}
}
// Apply Floyd-Warshall algorithm to find shortest paths
for (l = 0; l < numNodes; l++) {
#pragma omp parallel for shared(dist) private(i, j)
for (i = 0; i < numNodes; i++) {
for (j = 0; j < numNodes; j++) {
if (dist[i*numNodes + l] != INF && dist[l*numNodes + j] != INF
&& dist[i*numNodes + j] > dist[i*numNodes + l] + dist[l*numNodes + j]) {
dist[i*numNodes + j] = dist[i*numNodes + l] + dist[l*numNodes + j];
}
}
}
}
// Output the Kth shortest path from source to destination
printf("Kth Shortest Path from %d to %d:\n", source
, dest
); printf("Distance: %d\n", dist
[source
*numNodes
+ dest
]);
}
int main(int argc, char *argv[]) {
int numProcesses, rank;
int numNodes;
int **adjMatrix;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &numProcesses);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (argc < 2) {
if (rank == 0)
fprintf(stderr
, "Usage: %s <input_file>\n", argv
[0]); MPI_Finalize();
return 1;
}
readGraph(argv[1], &numNodes, &adjMatrix);
// Example usage: find the 1st shortest path from node 0 to node numNodes-1
int source = 0;
int dest = numNodes - 1;
int k = 1; // Find the 1st shortest path
// Perform Kth shortest path computation
kthShortestPath(numNodes, adjMatrix, source, dest, k);
// Clean up
for (int i = 0; i < numNodes; i++)
MPI_Finalize();
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPG1waS5oPgojaW5jbHVkZSA8b21wLmg+CiNpbmNsdWRlIDxsaW1pdHMuaD4KCiNkZWZpbmUgSU5GIElOVF9NQVgKCi8vIEZ1bmN0aW9uIHRvIHJlYWQgdGhlIGdyYXBoIGZyb20gYSBmaWxlCnZvaWQgcmVhZEdyYXBoKGNvbnN0IGNoYXIgKmZpbGVuYW1lLCBpbnQgKm51bU5vZGVzLCBpbnQgKioqYWRqTWF0cml4KSB7CiAgICBGSUxFICpmaWxlID0gZm9wZW4oZmlsZW5hbWUsICJyIik7CiAgICBpZiAoZmlsZSA9PSBOVUxMKSB7CiAgICAgICAgZnByaW50ZihzdGRlcnIsICJFcnJvcjogQ2Fubm90IG9wZW4gZmlsZSAlc1xuIiwgZmlsZW5hbWUpOwogICAgICAgIGV4aXQoMSk7CiAgICB9CgogICAgZnNjYW5mKGZpbGUsICIlZCIsIG51bU5vZGVzKTsKCiAgICAvLyBBbGxvY2F0ZSBtZW1vcnkgZm9yIGFkamFjZW5jeSBtYXRyaXgKICAgICphZGpNYXRyaXggPSAoaW50ICoqKW1hbGxvYygqbnVtTm9kZXMgKiBzaXplb2YoaW50ICopKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgKm51bU5vZGVzOyBpKyspIHsKICAgICAgICAoKmFkak1hdHJpeClbaV0gPSAoaW50ICopbWFsbG9jKCpudW1Ob2RlcyAqIHNpemVvZihpbnQpKTsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8ICpudW1Ob2RlczsgaisrKSB7CiAgICAgICAgICAgIGZzY2FuZihmaWxlLCAiJWQiLCAmKCphZGpNYXRyaXgpW2ldW2pdKTsKICAgICAgICAgICAgaWYgKCgqYWRqTWF0cml4KVtpXVtqXSA9PSAwICYmIGkgIT0gaikKICAgICAgICAgICAgICAgICgqYWRqTWF0cml4KVtpXVtqXSA9IElORjsgLy8gU2V0IHVucmVhY2hhYmxlIGVkZ2VzIHRvIElORgogICAgICAgIH0KICAgIH0KCiAgICBmY2xvc2UoZmlsZSk7Cn0KCi8vIEZ1bmN0aW9uIHRvIGNvbXB1dGUgS3RoIHNob3J0ZXN0IHBhdGggdXNpbmcgRmxveWQtV2Fyc2hhbGwgYWxnb3JpdGhtCnZvaWQga3RoU2hvcnRlc3RQYXRoKGludCBudW1Ob2RlcywgaW50ICoqYWRqTWF0cml4LCBpbnQgc291cmNlLCBpbnQgZGVzdCwgaW50IGspIHsKICAgIGludCAqZGlzdCA9IChpbnQgKiltYWxsb2MobnVtTm9kZXMgKiBudW1Ob2RlcyAqIHNpemVvZihpbnQpKTsKICAgIGludCBpLCBqLCBsOwoKICAgIC8vIEluaXRpYWxpemUgZGlzdGFuY2UgbWF0cml4CiAgICBmb3IgKGkgPSAwOyBpIDwgbnVtTm9kZXM7IGkrKykgewogICAgICAgIGZvciAoaiA9IDA7IGogPCBudW1Ob2RlczsgaisrKSB7CiAgICAgICAgICAgIGRpc3RbaSpudW1Ob2RlcyArIGpdID0gYWRqTWF0cml4W2ldW2pdOwogICAgICAgIH0KICAgIH0KCiAgICAvLyBBcHBseSBGbG95ZC1XYXJzaGFsbCBhbGdvcml0aG0gdG8gZmluZCBzaG9ydGVzdCBwYXRocwogICAgZm9yIChsID0gMDsgbCA8IG51bU5vZGVzOyBsKyspIHsKICAgICAgICAjcHJhZ21hIG9tcCBwYXJhbGxlbCBmb3Igc2hhcmVkKGRpc3QpIHByaXZhdGUoaSwgaikKICAgICAgICBmb3IgKGkgPSAwOyBpIDwgbnVtTm9kZXM7IGkrKykgewogICAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgbnVtTm9kZXM7IGorKykgewogICAgICAgICAgICAgICAgaWYgKGRpc3RbaSpudW1Ob2RlcyArIGxdICE9IElORiAmJiBkaXN0W2wqbnVtTm9kZXMgKyBqXSAhPSBJTkYKICAgICAgICAgICAgICAgICAgICAmJiBkaXN0W2kqbnVtTm9kZXMgKyBqXSA+IGRpc3RbaSpudW1Ob2RlcyArIGxdICsgZGlzdFtsKm51bU5vZGVzICsgal0pIHsKICAgICAgICAgICAgICAgICAgICBkaXN0W2kqbnVtTm9kZXMgKyBqXSA9IGRpc3RbaSpudW1Ob2RlcyArIGxdICsgZGlzdFtsKm51bU5vZGVzICsgal07CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgLy8gT3V0cHV0IHRoZSBLdGggc2hvcnRlc3QgcGF0aCBmcm9tIHNvdXJjZSB0byBkZXN0aW5hdGlvbgogICAgcHJpbnRmKCJLdGggU2hvcnRlc3QgUGF0aCBmcm9tICVkIHRvICVkOlxuIiwgc291cmNlLCBkZXN0KTsKICAgIHByaW50ZigiRGlzdGFuY2U6ICVkXG4iLCBkaXN0W3NvdXJjZSpudW1Ob2RlcyArIGRlc3RdKTsKICAgIAogICAgZnJlZShkaXN0KTsKfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgKmFyZ3ZbXSkgewogICAgaW50IG51bVByb2Nlc3NlcywgcmFuazsKICAgIGludCBudW1Ob2RlczsKICAgIGludCAqKmFkak1hdHJpeDsKCiAgICBNUElfSW5pdCgmYXJnYywgJmFyZ3YpOwogICAgTVBJX0NvbW1fc2l6ZShNUElfQ09NTV9XT1JMRCwgJm51bVByb2Nlc3Nlcyk7CiAgICBNUElfQ29tbV9yYW5rKE1QSV9DT01NX1dPUkxELCAmcmFuayk7CgogICAgaWYgKGFyZ2MgPCAyKSB7CiAgICAgICAgaWYgKHJhbmsgPT0gMCkKICAgICAgICAgICAgZnByaW50ZihzdGRlcnIsICJVc2FnZTogJXMgPGlucHV0X2ZpbGU+XG4iLCBhcmd2WzBdKTsKICAgICAgICBNUElfRmluYWxpemUoKTsKICAgICAgICByZXR1cm4gMTsKICAgIH0KCiAgICByZWFkR3JhcGgoYXJndlsxXSwgJm51bU5vZGVzLCAmYWRqTWF0cml4KTsKCiAgICAvLyBFeGFtcGxlIHVzYWdlOiBmaW5kIHRoZSAxc3Qgc2hvcnRlc3QgcGF0aCBmcm9tIG5vZGUgMCB0byBub2RlIG51bU5vZGVzLTEKICAgIGludCBzb3VyY2UgPSAwOwogICAgaW50IGRlc3QgPSBudW1Ob2RlcyAtIDE7CiAgICBpbnQgayA9IDE7IC8vIEZpbmQgdGhlIDFzdCBzaG9ydGVzdCBwYXRoCgogICAgLy8gUGVyZm9ybSBLdGggc2hvcnRlc3QgcGF0aCBjb21wdXRhdGlvbgogICAga3RoU2hvcnRlc3RQYXRoKG51bU5vZGVzLCBhZGpNYXRyaXgsIHNvdXJjZSwgZGVzdCwgayk7CgogICAgLy8gQ2xlYW4gdXAKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbnVtTm9kZXM7IGkrKykKICAgICAgICBmcmVlKGFkak1hdHJpeFtpXSk7CiAgICBmcmVlKGFkak1hdHJpeCk7CgogICAgTVBJX0ZpbmFsaXplKCk7CiAgICByZXR1cm4gMDsKfQo=