Инкрементация алгоритма Дейкстры.
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
http://codepad.org/AVsq8QaH – ссылка на код