Параллельная реализация Bellman-Ford

Question

Может ли кто-нибудь указать мне хороший псевдокод простого параллельного алгоритма кратчайшего пути? Или любой язык, это не имеет значения. У меня проблемы с поиском хороших примеров =[

Answer 1

В конце концов я сам реализовал это для биткойн-бота, используя OpenMP:

/*defines the chunk size as 1 contiguous iteration*/
#define CHUNKSIZE 1 
/*forks off the threads*/
#pragma omp parallel private(i) {
/*Starts the work sharing construct*/
#pragma omp for schedule(dynamic, CHUNKSIZE)
        list<list_node>::iterator i;
        for (int u = 0; u < V - 1; u++) {
            if (dist[u] != INT_MAX) {
                for (i = adj[u].begin(); i != adj[u].end(); ++i) {
                    if (dist[i->get_vertex()] > dist[u] + i->get_weight()) {
                        dist[i->get_vertex()] = dist[u] + i->get_weight();
                        pre[i->get_vertex()] = u;
                    }
                }
            }
        }
    }

Если вы хотите посмотреть на мою полную реализацию, вы можете просмотреть ее как Gist на моем GitHub