Instantly share code, notes, and snippets.

# evlogii/dijkstra.cpp

Last active December 29, 2015 07:09
Show Gist options
• Save evlogii/7633655 to your computer and use it in GitHub Desktop.
Инкрементация алгоритма Дейкстры.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #define NUM_VERTICES 5 #define SOURCE 0 // от этой вершины до всех остальных #include #include using namespace std; int main(int argc, char const *argv[]) { int myMatrix[NUM_VERTICES][NUM_VERTICES] = { // создаём матрицу инцидентности {INT_MAX, 3,INT_MAX,INT_MAX,INT_MAX}, {INT_MAX,INT_MAX, 1, 3,INT_MAX}, {INT_MAX,INT_MAX,INT_MAX, 1, 100}, {INT_MAX,INT_MAX,INT_MAX,INT_MAX, 50}, {INT_MAX,INT_MAX,INT_MAX,INT_MAX,INT_MAX} }; vector distance (NUM_VERTICES, INT_MAX); // вектор всех вершин vector visited (NUM_VERTICES, 0); // вектор посещённых вершин distance[SOURCE] = 0; //источник int vertex_min_dist = INT_MAX; int min_dist = INT_MAX; for (int i = 0; i < NUM_VERTICES; ++i) { // основной цикл тут происходит магия for (int j = 0; j < NUM_VERTICES; ++j) { if ((distance[j] < min_dist) && (visited[j] == 0)) { min_dist = distance[j]; vertex_min_dist = j; visited[j] = 1; } } for (int j = 0; j < NUM_VERTICES; ++j) { if (myMatrix[vertex_min_dist][j] < distance[j]) distance[j] = distance[vertex_min_dist] + myMatrix[vertex_min_dist][j]; } min_dist = INT_MAX; } for (int i = 0; i < NUM_VERTICES; ++i) { printf("minimum distance from %d to %d vertex = %d\n", SOURCE, i, distance[i]); } return 0; }