SHARE
TWEET

Untitled

a guest Jun 16th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // A C++ program for Dijkstra's single source shortest path algorithm.
  2. // The program is for adjacency matrix representation of the graph
  3.    
  4. #include <stdio.h>
  5. #include <limits.h>
  6.    
  7. // Number of vertices in the graph
  8. const int V = 16;
  9. const int IN_MAX = 9999;
  10.    
  11. // A utility function to find the vertex with minimum distance value, from
  12. // the set of vertices not yet included in shortest path tree
  13. int minDistance(int dist[], bool sptSet[])
  14. {
  15.    // Initialize min value
  16.    int min = INT_MAX, min_index;
  17.    
  18.    for (int v = 0; v < V; v++)
  19.      if (sptSet[v] == false && dist[v] <= min)
  20.          min = dist[v], min_index = v;
  21.    
  22.    return min_index;
  23. }
  24.    
  25. // A utility function to print the constructed distance array
  26. int printSolution(int dist[], int n)
  27. {
  28.    Serial.print("Intersections        /  Distance de la source en milim├Ętres\n");
  29.    for (int i = 0; i < V; i++){
  30.       Serial.print("");
  31.       Serial.print(i);
  32.       Serial.print("           / ");
  33.       Serial.println(dist[i]);
  34.    }
  35. }
  36.    
  37. // Function that implements Dijkstra's single source shortest path algorithm
  38. // for a graph represented using adjacency matrix representation
  39. void dijkstra(int graph[V][V], int src)
  40. {
  41.      int dist[V];     // The output array.  dist[i] will hold the shortest
  42.                       // distance from src to i
  43.    
  44.      bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
  45.                      // path tree or shortest distance from src to i is finalized
  46.    
  47.      // Initialize all distances as INFINITE and stpSet[] as false
  48.      for (int i = 0; i < V; i++)
  49.         dist[i] = INT_MAX, sptSet[i] = false;
  50.    
  51.      // Distance of source vertex from itself is always 0
  52.      dist[src] = 0;
  53.    
  54.      // Find shortest path for all vertices
  55.      for (int count = 0; count < V-1; count++)
  56.      {
  57.        // Pick the minimum distance vertex from the set of vertices not
  58.        // yet processed. u is always equal to src in the first iteration.
  59.        int u = minDistance(dist, sptSet);
  60.    
  61.        // Mark the picked vertex as processed
  62.        sptSet[u] = true;
  63.    
  64.        // Update dist value of the adjacent vertices of the picked vertex.
  65.        for (int v = 0; v < V; v++)
  66.    
  67.          // Update dist[v] only if is not in sptSet, there is an edge from  
  68.          // u to v, and total weight of path from src to  v through u is  
  69.          // smaller than current value of dist[v]
  70.          if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX  
  71.                                        && dist[u]+graph[u][v] < dist[v])
  72.             dist[v] = dist[u] + graph[u][v];
  73.      }
  74.    
  75.      // print the constructed distance array
  76.      printSolution(dist, V);
  77. }
  78.    
  79. // driver program to test above function
  80. void setup(){
  81.    Serial.begin(9600);
  82.  
  83. }
  84. void loop()
  85. {
  86.    /* Let us create the example graph discussed above */
  87.    int graph[V][V] = {  {0 , 1700 , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0   , 0  , 0   , 0 , 0  , 2790 },
  88.   {1700, 0  , 1380 , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 11480 , 0  , 0   , 0  , 0  , 0  },
  89.   {0 , 1380 , 0  , 1160 , 0  , 2080 , 0  , 0  , 0  , 0  , 0   , 0  , 0   , 0  , 0 , 0  },
  90.   {0 , 0  , 1160 , 0  , 2080 , 0  , 0  , 0  , 0  , 0  , 0   , 0  , 0   , 0  , 0  , 0  },
  91.   {0 , 0  , 0  , 2080 , 0  , 1160 , 0  , 0  , 6820 , 0  , 0   , 0  , 0  , 0  , 0  , 0  },
  92.   {0 , 0  , 2080 , 0  , 1160 , 0  , 0  , 6820 , 0  , 0  , 0   , 0  , 0   , 0  , 0  , 0  },
  93.   {0 , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0   , 8670 , 0   , 0  , 0  , 920 },
  94.   {0 , 0  , 0  , 0  , 0  , 6820 , 0  , 0  , 1040 , 0  , 0   , 0  , 0   , 0  , 0  , 0  },
  95.   {0 , 0 , 0  , 0  , 6820 , 0  , 0  , 1040 , 0  , 0  , 0   , 0  , 0   , 0  , 0  , 0  },
  96.   {0 , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 2600 , 0  , 2570  , 0  , 0   , 0  , 1300 , 0  },
  97.   {0 , 11480, 0  , 0  , 0 , 0  , 0  , 0  , 0  , 2570 , 0   , 670 , 0   , 1320 , 0  , 0  },
  98.   {0 , 0  , 0  , 0  , 0  , 0  , 8670 , 0  , 0  , 0  , 670  , 0  , 0   , 0  , 0  , 0  },
  99.   {0 , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0   , 0  , 0   , 4160 , 0  , 10010},
  100.   {0, 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 1320  , 0  , 1580  , 0  , 2580 , 0  },
  101.   {0 , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 0  , 1300  , 0   , 0  , 0   , 2580 , 0  , 0  },
  102.   {2790, 0  , 0  , 0  , 0  , 0  , 920 , 0  , 0  , 0  , 0   , 0  , 10010 , 0  , 0  , 0  }
  103.                      };
  104.    
  105.     dijkstra(graph, 1);
  106.    delay(50000);
  107. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top