Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Dijkstra'sshortest path algorithm.
- // The program is for adjacency matrix representation of the graph
- #include <stdio.h>
- #include <uart.h>
- #include <system/peripherals.h>
- #include <libacc.h>
- // Number of vertices in the graph
- #define V 24
- typedef char bool;
- #define true 1
- #define false 0
- #define INT_MAX 131071
- int printSolution(int dist[], int n) {
- printf("\r\nVertex Distance from Source\r\n");
- for (int i = 0; i < V; i++)
- printf("%d \t\t %d\r\n", i, dist[i]);
- }
- void dijkstra(int graph[V][V], int src) {
- int min = 0, min_index = 0, u = 0;
- // The output array. dist[i] will hold the shortest distance from src to i
- int dist[V];
- // sptSet[i] will true if vertex i is included in shortest
- // path tree or shortest distance from src to i is finalized
- bool sptSet[V];
- for (int i = 0; i < V; i++) {
- //NO_SYNTHESIS;
- dist[i] = INT_MAX, sptSet[i] = false;
- }
- //printSolution(dist, V);
- dist[src] = 0;
- // Find shortest path for all vertices
- for (int count = 0; count < V-1; count++) {
- // Pick the minimum distance vertex from the set of vertices not
- // yet processed. u is always equal to src in first iteration.
- min = INT_MAX;
- for (int v = 0; v < V; v++) {
- //NO_SYNTHESIS;
- if (sptSet[v] == false && dist[v] <= min) {
- min = dist[v];
- min_index = v;
- }
- }
- u = min_index;
- sptSet[u] = true;
- /*
- * Update dist value of the adjacent vertices of the picked vertex.
- * Update dist[v] only if is not in sptSet, there is an edge from
- * u to v, and total weight of path from src to v through u is
- * smaller than current value of dist[v]
- */
- for (int v = 0; v < V; v++) {
- //NO_SYNTHESIS;
- //printf("\r\n v: %d", v);
- if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
- //&& graph[u][v] < dist[v]) {
- && dist[u]+graph[u][v] < dist[v]) {
- dist[v] = dist[u] + graph[u][v];
- //dist[v] = graph[u][v];
- //printf("\r\n dist[v]: %d graph[u][v]: %d", dist[v],graph[u][v]);
- //printf("\r\n dist[u]: %d sptSet[v]: %d", dist[u],sptSet[v]);
- }
- }
- }
- printSolution(dist, V);
- }
- int main() {
- stdio_uart_open(UART_LIGHT_0);
- TIMER_0->limit = 131072; //2^17 = 0x20000
- TIMER_1->limit = 262143; //2^18 - 1 = 0x3ffff
- /* Example Graph */
- // int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
- // {4, 0, 8, 0, 0, 0, 0, 11,0},
- // {0, 8, 0, 7, 0, 4, 0, 0, 2},
- // {0, 0, 7, 0, 9, 14,0, 0, 0},
- // {0, 0, 0, 9, 0, 10,0, 0, 0},
- // {0, 0, 4, 0, 10,0, 2, 0, 0},
- // {0, 0, 0, 14,0, 2, 0, 1, 6},
- // {8, 11,0, 0, 0, 0, 1, 0, 7},
- // {0, 0, 2, 0, 0, 0, 6, 7, 0}
- // };
- int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
- {4, 0, 8, 0, 0, 0, 0, 11,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
- {0, 8, 0, 7, 0, 4, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
- {0, 0, 7, 0, 9, 14,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
- {0, 0, 0, 9, 0, 10,0, 0, 0, 0, 0, 6,15, 8, 0, 0, 0, 0,12, 0, 0, 0, 0 ,0},
- {0, 0, 4, 0, 10,0, 2, 0, 0, 0, 0,12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
- {0, 0, 0, 14,0, 2, 0, 1, 6, 0, 0, 0, 0, 0, 0, 0, 0, 4, 5, 0, 0, 0, 0 ,0},
- {8, 11,0, 0, 0, 0, 1, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0 ,0},
- {0, 0, 2, 0, 0, 0, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,13, 7, 0, 0, 0, 0, 0, 0, 0 ,0},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
- {0, 0, 0, 0, 6,12, 0, 0, 0, 0, 0, 0, 8, 0, 6, 0, 0, 0, 0, 0, 4, 0, 0 ,0},
- {0, 0, 0, 0,15, 0, 0, 0, 0, 0, 0, 8, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
- {0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 1, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
- {0, 0, 0, 0, 0, 0, 0, 0, 0,13, 0, 6, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,9},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0 ,0},
- {0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 2, 0, 5, 0, 0 ,0},
- {0, 0, 0, 0,12, 0, 5, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 3, 0, 0, 0 ,0},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0 ,0},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0 ,0},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ,0},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ,2},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 2 ,0}
- };
- printf("\r\n === Dijkstra Algorithm ===\r\n");
- // HW Execution
- libacc_enable_accels();
- TIMER_0->control |= TIMER_CNT_RST;
- TIMER_0->control &= !TIMER_CNT_RST;
- TIMER_1->control |= TIMER_CNT_RST;
- TIMER_0->control &= !TIMER_CNT_RST;
- TIMER_1->control = TIMER_EN;
- TIMER_0->control = TIMER_EN;
- dijkstra(graph, 0);
- TIMER_0->control = 0;
- TIMER_1->control = 0;
- printf("\r\n HW timer value: %6u ov: %6u", TIMER_0->value, TIMER_1->value);
- // SW Execution
- libacc_disable_accels();
- TIMER_0->control |= TIMER_CNT_RST;
- TIMER_0->control &= !TIMER_CNT_RST;
- TIMER_1->control |= TIMER_CNT_RST;
- TIMER_0->control &= !TIMER_CNT_RST;
- TIMER_1->control = TIMER_EN;
- TIMER_0->control = TIMER_EN;
- dijkstra(graph, 0);
- TIMER_0->control = 0;
- TIMER_1->control = 0;
- printf("\r\n SW timer value: %6u ov: %6u", TIMER_0->value, TIMER_1->value);
- while(1);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement