fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <mpi.h>
  4. #include <omp.h>
  5. #include <limits.h>
  6.  
  7. #define INF INT_MAX
  8.  
  9. // Function to read the graph from a file
  10. void readGraph(const char *filename, int *numNodes, int ***adjMatrix) {
  11.     FILE *file = fopen(filename, "r");
  12.     if (file == NULL) {
  13.         fprintf(stderr, "Error: Cannot open file %s\n", filename);
  14.         exit(1);
  15.     }
  16.  
  17.     fscanf(file, "%d", numNodes);
  18.  
  19.     // Allocate memory for adjacency matrix
  20.     *adjMatrix = (int **)malloc(*numNodes * sizeof(int *));
  21.     for (int i = 0; i < *numNodes; i++) {
  22.         (*adjMatrix)[i] = (int *)malloc(*numNodes * sizeof(int));
  23.         for (int j = 0; j < *numNodes; j++) {
  24.             fscanf(file, "%d", &(*adjMatrix)[i][j]);
  25.             if ((*adjMatrix)[i][j] == 0 && i != j)
  26.                 (*adjMatrix)[i][j] = INF; // Set unreachable edges to INF
  27.         }
  28.     }
  29.  
  30.     fclose(file);
  31. }
  32.  
  33. // Function to compute Kth shortest path using Floyd-Warshall algorithm
  34. void kthShortestPath(int numNodes, int **adjMatrix, int source, int dest, int k) {
  35.     int *dist = (int *)malloc(numNodes * numNodes * sizeof(int));
  36.     int i, j, l;
  37.  
  38.     // Initialize distance matrix
  39.     for (i = 0; i < numNodes; i++) {
  40.         for (j = 0; j < numNodes; j++) {
  41.             dist[i*numNodes + j] = adjMatrix[i][j];
  42.         }
  43.     }
  44.  
  45.     // Apply Floyd-Warshall algorithm to find shortest paths
  46.     for (l = 0; l < numNodes; l++) {
  47.         #pragma omp parallel for shared(dist) private(i, j)
  48.         for (i = 0; i < numNodes; i++) {
  49.             for (j = 0; j < numNodes; j++) {
  50.                 if (dist[i*numNodes + l] != INF && dist[l*numNodes + j] != INF
  51.                     && dist[i*numNodes + j] > dist[i*numNodes + l] + dist[l*numNodes + j]) {
  52.                     dist[i*numNodes + j] = dist[i*numNodes + l] + dist[l*numNodes + j];
  53.                 }
  54.             }
  55.         }
  56.     }
  57.  
  58.     // Output the Kth shortest path from source to destination
  59.     printf("Kth Shortest Path from %d to %d:\n", source, dest);
  60.     printf("Distance: %d\n", dist[source*numNodes + dest]);
  61.  
  62.     free(dist);
  63. }
  64.  
  65. int main(int argc, char *argv[]) {
  66.     int numProcesses, rank;
  67.     int numNodes;
  68.     int **adjMatrix;
  69.  
  70.     MPI_Init(&argc, &argv);
  71.     MPI_Comm_size(MPI_COMM_WORLD, &numProcesses);
  72.     MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  73.  
  74.     if (argc < 2) {
  75.         if (rank == 0)
  76.             fprintf(stderr, "Usage: %s <input_file>\n", argv[0]);
  77.         MPI_Finalize();
  78.         return 1;
  79.     }
  80.  
  81.     readGraph(argv[1], &numNodes, &adjMatrix);
  82.  
  83.     // Example usage: find the 1st shortest path from node 0 to node numNodes-1
  84.     int source = 0;
  85.     int dest = numNodes - 1;
  86.     int k = 1; // Find the 1st shortest path
  87.  
  88.     // Perform Kth shortest path computation
  89.     kthShortestPath(numNodes, adjMatrix, source, dest, k);
  90.  
  91.     // Clean up
  92.     for (int i = 0; i < numNodes; i++)
  93.         free(adjMatrix[i]);
  94.     free(adjMatrix);
  95.  
  96.     MPI_Finalize();
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout #stderr 0.28s 40732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected '/' in "/"
Execution halted
https://ideone.com/YtUII5
language:
R (R 3.5.2)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!