Instantly share code, notes, and snippets.

Embed
What would you like to do?
Инкрементация алгоритма Дейкстры.
#define NUM_VERTICES 5
#define SOURCE 0 // от этой вершины до всех остальных
#include <limits>
#include <vector>
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<int> distance (NUM_VERTICES, INT_MAX); // вектор всех вершин
vector<bool> 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;
}
@evlogii

This comment has been minimized.

Show comment
Hide comment
@evlogii

evlogii Nov 24, 2013

http://codepad.org/AVsq8QaH – ссылка на код

Owner

evlogii commented Nov 24, 2013

http://codepad.org/AVsq8QaH – ссылка на код

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment