Алгоритм кратчайшего пути для взвешенных графов, ориентированный на веб-сборку

У меня есть код C, который берет ребра взвешенного графа и некоторую точку
Он возвращает минимальные расстояния от точки a до других и предыдущей точки пути, которые имеют минимальную длину (лучший способ).

Например, если лучший способ — a → b → c:

• предыдущая точка для a равна нулю / -1 / -2 …
• предыдущая точка для b — это
• предыдущая точка для c — b

#include <stdio.h>
#include <stdint.h>

int edges_start[3000];
int edges_end[3000];
float edges_len[3000];

int g_links_id[1000][100];
float g_links_weight[1000][100];

int cache_id[1000];
float cache_distance[1000];
int cache_prev[1000];
int cache_links_id[1000][100];
float cache_links_weight[1000][100];

int queue_id[1000];
float queue_distance[1000];
int queue_prev[1000];
int queue_links_id[1000][100];
float queue_links_weight[1000][100];

int queue_links_id_len[1000];

// MUSL memset implementation:
// https://github.com/esmil/musl/blob/master/src/string/memset.c

#include <stdint.h>
#include <string.h>

void* __attribute__((weak)) memset(void* dest, int c, size_t n)
{
    unsigned char* s = dest;
    size_t k;

    if(!n)
    {
        return dest;
    }

    s[0] = s[n - 1] = (unsigned char)c;

    if(n <= 2)
    {
        return dest;
    }

    s[1] = s[n - 2] = (unsigned char)c;
    s[2] = s[n - 3] = (unsigned char)c;

    if(n <= 6)
    {
        return dest;
    }

    s[3] = s[n - 4] = (unsigned char)c;

    if(n <= 8)
    {
        return dest;
    }


    k = -(uintptr_t)s & 3;
    s += k;
    n -= k;
    n &= (unsigned long)-4;
    n /= 4;

    // Cast to void first to prevent alignment warning
    uint32_t* ws = (uint32_t*)(void*)s;
    uint32_t wc = c & 0xFF;
    wc |= ((wc << 8) | (wc << 16) | (wc << 24));

    /* Pure C fallback with no aliasing violations. */
    for(; n; n--, ws++)
    {
        *ws = wc;
    }

    return dest;
}


#include <string.h>

typedef int word; 

#define wsize sizeof(word)
#define wmask (wsize - 1)

void* memcpy(void* dst0, const void* src0, size_t length)
{
    char* dst = dst0;
    const char* src = src0;
    size_t t;

    if(length == 0 || dst == src)
    {
        /* nothing to do */
        goto done;
    }

#define TLOOP(s) if 
#define TLOOP1(s) do { s; } while (--t)


    if((uintptr_t)dst < (uintptr_t)src)
    {

        t = (uintptr_t)src; /* only need low bits */
        if((t | (uintptr_t)dst) & wmask)
        {
            
            if((t ^ (uintptr_t)dst) & wmask || length < wsize)
            {
                t = length;
            }
            else
            {
                t = wsize - (t & wmask);
            }
            length -= t;
            TLOOP1(*dst++ = *src++);
        }
    
        t = length / wsize;
        // Silence warning for alignment change by casting to void*
        TLOOP(*(word*)(void*)dst = *(const word*)(const void*)src; src += wsize; dst += wsize);
        t = length & wmask;
        TLOOP(*dst++ = *src++);
    }
    else
    {
    
        src += length;
        dst += length;
        t = (uintptr_t)src;

        if((t | (uintptr_t)dst) & wmask)
        {
            if((t ^ (uintptr_t)dst) & wmask || length <= wsize)
            {
                t = length;
            }
            else
            {
                t &= wmask;
            }

            length -= t;
            TLOOP1(*--dst = *--src);
        }

        t = length / wsize;
        // Silence warning for alignment change by casting to void*
        TLOOP(src -= wsize; dst -= wsize; *(word*)(void*)dst = *(const word*)(const void*)src);
        t = length & wmask;
        TLOOP(*--dst = *--src);
    }
done:
    return (dst0);
}


void init_cpp(int L) {
  for (int i=0; i < L; i++) {
    queue_links_id_len[i] = 0;
    cache_id[i] = -2;
    queue_id[i] = -2;
    cache_distance[i] =  100000;
    queue_distance[i] = 100000;
    cache_prev[i] = -2;
    queue_prev[i] = -2;
    for (int j=0; j < 100; j++) {
      queue_links_id[i][j] = -2;
      queue_links_weight[i][j] = 100000;
      cache_links_id[i][j] = -2;
      cache_links_weight[i][j] = 100000;
    }
  }
}

void init_edges_cpp() {
  for (int i=0; i < 3000; i++) {
    edges_start[i] = -2;
    edges_end[i] = -2;
    edges_len[i] = -2.0;
  }

  for (int i=0; i < 1000; i++) {
    for (int j=0; j < 100; j++) {
      g_links_id[i][j] = -2;
      g_links_weight[i][j] = -2.0;
    }
  }
}

void add_edge_cpp(int index, int start, int end, float len) {
  edges_start[index] = start;
  edges_end[index] = end;
  edges_len[index] = len;
}

void fill_graph_cpp() {
  for (int i=0; i < 3000; i++) {
    int s = edges_start[i];
    int e = edges_end[i];
    float len = edges_len[i];

    if (s == -2) {
      break;
    }

    int links_len = 0;

    for (int j=0; j < 100; j++) {
      if (g_links_id[s][j] == -2) {
        links_len = j;
        break;
      }
    }

    g_links_id[s][links_len] = e;
    g_links_weight[s][links_len] = len;

    for (int j=0; j < 100; j++) {
      if (g_links_id[e][j] == -2) {
        links_len = j;
        break;
      }
    }
    g_links_id[e][links_len] = s;
    g_links_weight[e][links_len] = len;
  }
}


void get_dists_cpp(int a, int L) {
  

    int i = L;
    while (--i >= 0) {
        
        
        for (int j = 0; j < 100; j++) {
            //console.log()
            if (g_links_id[i][j] == -2) {
                break;
            }
            cache_links_id[i][j] = g_links_id[i][j];
            cache_links_weight[i][j] = g_links_weight[i][j];
        }

        cache_id[i] = i;
    }


    queue_id[0] = cache_id[a];
    cache_distance[a] = 0;
    queue_distance[0] = cache_distance[a];
    queue_prev[0] = queue_prev[a];
    
    for (int j=0; j < 100; j++) {
      if (cache_links_id[a][j] == -2) {
        queue_links_id_len[0] = j;
        break;
      }
        queue_links_id[0][j] = cache_links_id[a][j];
        queue_links_weight[0][j] = cache_links_weight[a][j];
    }
    
  
    
    i=0;
    int queue_len = 1;
    while (i < queue_len) {
        int node_id = queue_id[i];
        float node_distance = queue_distance[i];
        int node_prev = queue_prev[i];
      
      /*
        int j=0;
        for (int k=0; k < 100; k++) {
            if (queue_links_id[i][k] == -2) {
                j=k;
                break;
            }
        }
        */
        
        int j = queue_links_id_len[i];

        while (--j >= 0) {
            int link_id = queue_links_id[i][j];
            float link_weight = queue_links_weight[i][j];

            int c_id = cache_id[link_id];
            float c_distance = cache_distance[link_id];
            int c_prev = cache_prev[link_id];

            float d = node_distance + link_weight;
            if (d <= c_distance) {
                cache_prev[link_id] = node_id;
                cache_distance[link_id] = d;

                
                queue_id[queue_len] = cache_id[link_id];
                queue_distance[queue_len] = cache_distance[link_id];

                for (int k=0; k < 100; k++) {
                    if (cache_links_id[link_id][k] == -2) {
                      queue_links_id_len[queue_len] = k;
                        break;
                    }
                    
            queue_links_id[queue_len][k] = cache_links_id[link_id][k];
            queue_links_weight[queue_len][k] = cache_links_weight[link_id][k];
          }
          queue_prev[queue_len] = cache_prev[link_id];
          queue_len++;
            }

        }
        i++;
    }

}

int get_edges_start(int index) {
  return edges_start[index];
}

float get_cache_distance(int index) {
    return cache_distance[index];
}

int get_cache_prev(int index) {
    return cache_prev[index];
}



int main() {
    init_edges_cpp();
    init_cpp(5);
    add_edge_cpp(0, 0, 2, 1);
    add_edge_cpp(1, 0, 1, 1);
    add_edge_cpp(2, 1, 2, 1);
    add_edge_cpp(3, 2, 3, 1);
    add_edge_cpp(4, 2, 4, 1);
    add_edge_cpp(5, 3, 4, 1);
    fill_graph_cpp();
    
    get_dists_cpp(0, 5);
    
    for (int i=0; i < 5; i++) {
        printf("vert: %d ", i);
        printf("dist: %f ", get_cache_distance(i));
        printf("prev: %dn", get_cache_prev(i));
    }
    
    
    return 0;
}

Вы можете запустите этот код онлайн.

Я добавил кодовые реализации memcpy и memset потому что мне нужно скомпилировать этот код в wasm с помощью эта услуга. Так что мне нужны эти реализации.

Также я не использовал расширенные структуры, потому что это делает невозможным (или очень-очень сложным) компиляцию кода для веб-сборки.

Я думаю, что код можно сделать быстрее. Как мне сделать это быстрее?