Djikstra

gistfile1.cpp

#include <iostream>
#include <stdio.h>
#include <string>
#include <queue>
#include <stack>


using namespace std;


const int w = 1000;
const int MAX = 10000000;
int weights[w][w];


int minim(int a, int b) {
	return a < b ? a : b;
}

int djikstra(int s, int e, int n){
	queue<int> x;
	int optimal[w];
	for (int j = 0; j < n; j++)
		optimal[j] = MAX;
	optimal[s] = 0;

	x.push(s);

	bool visited[w];

	for (int i = 0; i < n; i++)
		visited[i] = 0;

	while (x.size()>0){
		int source = x.front();
		visited[source] = 1;
		x.pop();
		for (int j = 0; j < n; j++){
			int neighbourWeight = weights[source][j];
			if (neighbourWeight != -1 && !visited[j] && neighbourWeight != 0){
				optimal[j] = minim(optimal[j], optimal[source] + neighbourWeight);
			}
		}
		int minind = -1, minval = MAX;

		for (int i = 0; i < n; i++){
			if (!visited[i]){
				if (optimal[i] < minval){
					minval = optimal[i];
					minind = i;
				}
			}
		}
		if (minind != -1)
			x.push(minind);
	}
	return optimal[e];
}

int main()
{
	cout << "Enter vertecies count : ";
	int n;
	cin >> n;

	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			cout << "Enter weight between vertex " << i << " and vertex " << j << " :";
			cin >> weights[i][j];
			cout << endl;
		}
	}
	while (1){
		cout << "Enter start and end point : ";
		int s, e;
		cin >> s >> e;
		int ans = djikstra(s, e, n);
		cout << "Minimal distance is : " << ans << endl;
	}
	return 0;
}