Инкрементация алгоритма Дейкстры.

dijkstra.cpp

#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;
}

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