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