include iostream include time include conio include vector include que

#include <iostream>
#include <time.h>
#include <conio.h>
#include <vector>
#include <queue>
using namespace std;
void search(bool *passed, int unit, int **GM, int n){
	vector <int> par;
	int i = 0,j = 0;
	int *queue=new int[n];
	int * d = (int *) calloc(n, sizeof(int));
	int count, head;
	for (i=0; i<n; i++) 
		queue[i]=0;
	count=0; head=0;
	queue[count++]=unit;
	passed[unit]=true;
	while (head<count){
		unit=queue[head++];
		//cout << unit << " ";
		par.push_back(unit);
		for (i=0; i<n; i++)
			if (GM[unit][i] && !passed[i]){
				queue[count++]=i;
				d[i] = d[unit] + 1;
				passed[i]=true;
			}
	}
	bool done = false;
	int dd = 0;
	while (!done){
		done = true;
		cout << "( ";
		for (int i = 0; i<n; ++i){
			if (d[i] == dd && passed[i]){
				cout << i << ' ';
			}
			if (d[i] == dd + 1) done = false;
		}
		cout << ")";
		if (!done) cout << endl;
		++dd;
	}
	cout << endl;
	vector <int> :: iterator r;
	cout << "Каркас:" << endl;
	for ( r = par.begin(); r < par.end(); r++)
		cout << *r << " ";
	cout << endl;
	free(d);
	delete []queue;
}
void Shir()
{
	cout << "Поиск в ширину:" << endl;
	int n;
	cout << "Введите количество вершин: " ;
	cin >> n;
	cout << endl;
	bool *vis=new bool[n];
	int **GM;
	int start,i,j;
	srand(time(NULL));
   GM = (int**)malloc(n*sizeof(int));
   for ( i = 0; i < n ; i ++)
	   GM[i] = (int*)calloc(n,sizeof(int));
   for( i = 0; i < n; i++)
	   for ( j = 0; j < n; j++)
		   GM[i][j] = rand()%2;
	   for ( i = 0; i < n ; i++)
		   for ( j = 0; j <n; j++){
			   GM[i][j] = GM[j][i];
			   GM[i][i] = 0;
		   }
        cout<<"Матрица: "<<endl;
               for (i=0; i<n; i++){
				   vis[i]=false;
				   for (j=0; j<n; j++)
					   cout  << " " << GM[i][j];
				   cout<<endl;
			   }
         cout<<"Введите стартовую вершину: ";
           cin>>start;
               cout<<"Путь: " << endl;
			   search(vis, start, GM, n);
			  // bfs(start,GM,vis,n);
			   delete []vis;
			   for ( i = 0; i < n; i++)
				   free(GM[i]);
			   free(GM);
}
void Gsearch(int st, int **graph, bool *visited, int n){
	int r;
	visited[st]=true;
	for (r=0; r<n; r++)
		if ((graph[st][r]) && (!visited[r])){
			cout << st << " -> " << r << endl;
			Gsearch(r, graph, visited, n);
		}
}
void Glub(){
	cout << "Поиск в глубину:" << endl;
	int n=5;
	cout << "Введите количество вершин: " ;
	cin >> n;
	cout << endl;
	int i, j,start;
	bool *visited=new bool[n];
	int **graph;
	int **tree;
	srand(time(NULL));
	graph = (int**)malloc(n*sizeof(int));
	tree = (int**)malloc(n*sizeof(int));
	for ( i = 0; i < n ; i ++)
	   graph[i] = (int*)calloc(n,sizeof(int));
	   tree[i] = (int*)calloc(n,sizeof(int));
    for( i = 0; i < n; i++)
	   for ( j = 0; j < n; j++)
		   graph[i][j] = rand()%2;
	for( i = 0; i < n; i++)
	   for ( j = 0; j < n; j++){
		   graph[i][j] = graph[j][i];
		   graph[i][i] = 0;
	   }
        cout<<"Матрица: "<<endl;
		for (i=0; i<n; i++){
			visited[i]=false;
			for (j=0; j<n; j++)
				cout<<" "<<graph[i][j];
			cout<<endl;
		}
		cout<<"Введите стартовую вершину: "; cin>>start;
		cout<<"Каркас:" << endl;
		Gsearch(start,graph,visited,n);
		delete []visited;
}

void Dijsearch(int **GR, int st,int V){
	int *distance = (int*)malloc(V*sizeof(int));
	int count, index, i, u, m=st+1;
	bool *visited = (bool*)malloc(V*sizeof(bool));
	for (i=0; i<V; i++){
		distance[i]=INT_MAX; 
		visited[i]=false;
	}
	distance[st]=0;
	for (count=0; count<V-1; count++)
	{
		int min=INT_MAX;
		for (i=0; i<V; i++)
			if (!visited[i] && distance[i]<=min)
			{
				min=distance[i]; index=i;
			}
			u=index;
			visited[u]=true;
			for (i=0; i<V; i++)
				if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX && distance[u]+GR[u][i]<distance[i])
					distance[i]=distance[u]+GR[u][i];
	}
	cout<<"Расстояние от стартовой вершины до остальных:\t\n";
	for (i=0; i<V; i++) 
		if (distance[i]!=INT_MAX)
			cout<<m<<" => "<<i+1<<" = "<<distance[i]<<endl;
	else 
		cout<<m<<" => "<<i+1<<" = "<<"отстутствует свзяь между вершинами"<<endl;
	free(distance);
	free(visited);
}
void Dij(int **mas, int V)
{
	cout << "Алгоритм Дейкстры:" << endl;
   int  n,start = 0, i, j;
	/*cout << "Введите количество вершин: " ;
	cin >> n;
	cout << endl;
	V = n;*/
   
//   srand(time(NULL));
    /*for( i = 0; i < V; i++)
	   for ( j = 0; j < V; j++){
		   mas[i][j] = (rand()%10)%2;
		   if (mas[i][j]) 
			   mas[i][j] = rand()%10;
	   }
    for( i = 0; i < V; i++)
		for ( j = 0; j < V; j++){
			mas[i][j] = mas[j][i];
			mas[i][i] = 0;
		}*/
	cout<<"Матрица: "<<endl;
		for (i=0; i<V; i++){
			for (j=0; j<V; j++)
				cout<<" "<<mas[i][j];
			cout<<endl;
		}
		cout << "Введите стартовую вершину: "; 
		cin>>start;
		Dijsearch(mas, start-1, V);
		/*for ( i = 0; i < V; i++)
		   free(mas[i]);
		free(mas);*/
}
void Floyd(){
	cout << "Алгоритм Флойда:" << endl;
	int **D;
	int k, j, n, i, V;
	cout<<"Введите количество вершин: ";
	cin>>V;
	n = V;
    D = (int**)malloc(V*sizeof(int));
	for ( i = 0; i < V ; i ++)
	   D[i] = (int*)calloc(V,sizeof(int));
	srand(time(NULL));
	for (i=0; i<n; i++)
		for (j=0; j<n; j++){
			D[i][j] = (rand()%10)%2;
			if(D[i][j])
				D[i][j] = rand()%10;
		}
	for( i = 0; i < n; i++)
		for ( j = 0; j < n; j++)
		{
			D[i][j] = D[j][i];
			D[i][i] = 0;
		}
	for (i=0; i<n; i++){
		for (j=0; j<n; j++)
			cout << D[i][j] << " ";
		cout << endl;
	}
	for (i=0; i<V; i++)
		D[i][i]=0;
	for (k=0; k<V; k++)
		for (i=0; i<V; i++)
			for (j=0; j<V; j++)
				if (D[i][k] && D[k][j] && i!=j)
					if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
						D[i][j]=D[i][k]+D[k][j];
	
	
    cout<<"Матрица лучших маршрутов:"<<endl;
       for (i=0; i<V; i++){
		for (j=0; j<V; j++)
			cout<<D[i][j]<<"\t";
        cout<<endl;
	}
}
#define INF 1000000
struct struc{
    int u;
	int v;
	int w;
};
const int firstpart=1000;
const int secondpart = firstpart*(firstpart-1)/2;
int i, j, n, e, start;
struc graph[secondpart];
int d[firstpart];
void bf(int n, int s){
	for (i=0; i<n; i++) 
		d[i]=INF;
	d[s]=0;
	for (i=0; i<n-1; i++)
		for (j=0; j<e; j++)
			if (d[graph[j].v]+graph[j].w<d[graph[j].u])
				d[graph[j].u]=d[graph[j].v]+graph[j].w;
	for (i=0; i<n; i++)
		if (d[i]==INF)
			cout<<endl<<start<<"=>"<<i+1<<"="<<"отстутствует свзяь между вершинами";
		else 
			cout<<endl<<start<<"=>"<<i+1<<"="<<d[i];
cout << endl;
}
void ford(){
	cout << "Алгоритм Форда - Беллмана:" << endl;
	int w;
	cout<<"Введите количество вершин: "; 
	cin>>n;
	e=0;
	//int V = n;
	int **mas;
   mas = (int**)malloc(n*sizeof(int));
	for ( i = 0; i < n ; i ++)
	   mas[i] = (int*)calloc(n,sizeof(int));
	srand(time(NULL));
	for (i=0; i<n; i++){
		for (j=0; j<n; j++){
			w = (rand()%10)%2;
			if(w) w = rand()%10;
			if (w!=0)
			{
				graph[e].v=i;
				graph[e].u=j;
				if ( i == j){
				w=0;
				}
				else
					graph[e].w=w;
				e++;
			}
			cout << w << " ";
			mas[i][j] = w;
		}
		cout << endl;
}

		cout<<"Введите стартовую вершину: "; 
		cin>>start;
	    cout<<"Расстояние от стартовой вершины до остальных:";
		bf(n, start-1);
		Dij(mas, n);
}
int main(){
 setlocale(LC_ALL, "Rus");
 //Shir();
 //Glub();
 ford();
}