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. OK, I Understand
 
Top