• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Sep 18th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <stdbool.h>
2. #include <stdlib.h>
3.
4. void trace_path(unsigned int *path, unsigned int *count, unsigned int *parents, unsigned int index) {
5.     unsigned int parent = parents[index];
6.     // found root node
7.     if (parent == ~0) return;
8.     // traverse down
9.     trace_path(path, count, parents, parent);
10.     // add node into path
11.     path[*count] = index;
12.     *count += 1;
13. }
14.
15. unsigned int min_distance(unsigned int *dist, bool *marked, unsigned int n) {
16.     unsigned int min_index;
17.     unsigned int min_dist = ~0; // max distance possible
18.     for (unsigned int i = 0; i < n; i += 1) if (marked[i] && dist[i] < min_dist) min_dist = dist[min_index = i];
19.     return min_index;
20. }
21.
22. // find shortest path between start node and end node
23. // start node is not included in path
24. // returns amounts of node in path
25. unsigned int dijkstra(
26.     unsigned int *graph,
27.     unsigned int n,
28.     unsigned int *path,
29.     unsigned int start,
30.     unsigned int stop
31. ) {
32.     bool *marked = malloc(n * sizeof * marked);
33.     unsigned int *dist = malloc(n * sizeof *dist); // shortest distance from start node to that node
34.     unsigned int *parents = malloc(n * sizeof *parents); // parent of this node
35.     // init data
36.     for (unsigned int i = 0; i < n; i++) {
37.         marked[i] = true;
38.         dist[i] = ~0; // max distance possible
39.         parents[i] = ~0; // root node
40.     }
41.     dist[start] = 0; // distance to itself is always 0
42.     // find shortest path for all node
43.     for (unsigned int c = 0; c < n; c += 1) {
44.         // pick nearest node from current data
45.         unsigned int u = min_distance(dist, marked, n);
46.         marked[u] = false;
47.         // update distance of adjacent node of picked node
48.         for (unsigned int v = 0; v < n; v += 1) {
49.             unsigned int ndist = dist[u] + graph[v + u * n];
50.             if (marked[v] && graph[v + u * n] && dist[v] > ndist) {
51.                 parents[v] = u;
52.                 dist[v] = ndist;
53.             }
54.         }
55.     }
56.     // traverse parents and copy to path
57.     unsigned int count = 0;
58.     trace_path(path, &count, parents, stop);
59.     free(parents);
60.     free(marked);
61.     free(dist);
62.     return count;
63. }
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