• API
• FAQ
• Tools
• Archive
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.

Top