Advertisement
Infernale

Dijkstra with paths

Dec 2nd, 2018
475
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <limits.h>
  3. using namespace std;
  4.  
  5. #define FOR(i, x, v) for(int i=x;i<v;i++)
  6. #define V 9
  7.  
  8. void printPath(int points[], int i){
  9.     if(points[i]==-1){
  10.         return;
  11.     }
  12.     printPath(points, points[i]);
  13.     cout << i << " ";
  14. }
  15.  
  16. void printSolution(int dist[], int points[]) {
  17.    printf("Titik   Jarak dari titik awal\tPath\n");
  18.    FOR(i, 0, V){
  19.       printf("%d \t\t %d \t\t ", i, dist[i]);
  20.       printPath(points, i);
  21.       cout << endl;
  22.     }
  23. }
  24.  
  25. int findMin(int dist[], bool visited[]){
  26.     int min = INT_MAX, minIndex;
  27.     FOR(i, 0, V){
  28.         if(visited[i]==false && dist[i]<=min){
  29.             minIndex = i;
  30.             min = dist[i];
  31.         }      
  32.     }
  33.     cout << "Min is " << minIndex << endl;
  34.     return minIndex;
  35. }
  36.  
  37. void shortestPath(int data[V][V], int fPoint){
  38.     int dist[V];
  39.     int points[V];
  40.     bool visited[V] = {false};
  41.     FOR(i, 0, V){
  42.         dist[i] = INT_MAX;
  43.     }
  44.     dist[fPoint] = 0;
  45.     points[fPoint] = -1;
  46.     FOR(i, 0, V-1){
  47.         int x = findMin(dist, visited);
  48.         visited[x] = true;
  49.         FOR(y, 0, V){
  50.             if(!visited[y] && data[x][y] && dist[x]!=INT_MAX && dist[x]+data[x][y]<dist[y]){
  51.                 dist[y] = dist[x] + data[x][y];
  52.                 cout << "Dist y is " << dist[y] << endl;
  53.                 points[y] = x;
  54.             }
  55.         }
  56.     }
  57.     printSolution(dist, points);
  58. }
  59.  
  60. int main(){
  61.    int data[V][V]   = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
  62.                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
  63.                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
  64.                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
  65.                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
  66.                       {0, 0, 4, 14, 10, 0, 2, 0, 0},
  67.                       {0, 0, 0, 0, 0, 2, 0, 1, 6},
  68.                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
  69.                       {0, 0, 2, 0, 0, 0, 6, 7, 0}};
  70.    
  71.     shortestPath(data, 0);
  72.     return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement