Добавил:
Studfiles2
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:СиАОД3
.CPP#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <graphics.h>
#include <string.h>
//Њ ЄбЁ¬ «м®Ґ ў®««ЁзҐбвў® ўҐаиЁ
#define uV 5
//Њ ЄбЁ¬ «м®Ґ Є®«зҐбвў® ॡҐа (ў १г«м ⥠Ї®«гз Ґ¬ +-2)
#define uE 7
//Њ ЄбЁ¬ «мл© ўҐб, Ў®«миҐ Є®в®а®Ј® 㦥 бзЁв Ґвбп а §алў®¬ ў Ја дҐ
#define maxWT 10000
//Њ ЄбЁ¬ «мл© ўҐб ॡа ,Є®в®ал© ¬®¦Ґв Ўлвм бЈҐҐаЁа®ў
#define maxWTreal 3
typedef struct stapex *tapex;
typedef struct stapex l;
typedef struct sGraph *Graph;
//‘вагЄвага i-в®© ўҐаиЁл ў бЇЁбЄҐ ᬥ¦®бвЁ
struct sGraph
{
int V,E;//-Є®«-ў® ўҐаиЁ, Є®«-ў® ॡҐа
float **adj;//-¬ ббЁў ᯨ᪠ᬥ¦®бвЁ
};
//€ЁжЁ «Ё§ жЁп бвагЄвгал Ја д Ёб室묨 § 票ﬨ
Graph initGrph(int V)
{
int v;
Graph G=(Graph)malloc(sizeof(struct sGraph));
G->V=V; G->E=0;
G->adj=(float**)malloc(sizeof(float)*V);
for(v=0;v<V;)
{
G->adj[v]=(float*)malloc(sizeof(float)*V);;
v++;
};
return G;
};
Graph randGrph(int V, int E)
{
int i,j;
double p=2.0*E/V/(V-1);
Graph G=initGrph(V);
for(i=0;i<V;i++)
for(j=0;j<i+1;j++)
{
if(rand() < p * RAND_MAX)
G->adj[i][j]=(float)random(10)/(random(5)+1);
else
G->adj[i][j]=maxWT;
if(j==i)
G->adj[i][i]=0;
else
G->adj[j][i]=G->adj[i][j];
};
return G;
};
Graph clearGrph(Graph G)
{
for(int i=0;i<G->V;i++)
free(G->adj[i]);
free(G->adj);
free(G);
return NULL;
};
void outGrph(Graph G)
{
float **A=G->adj;
int sign,dec;
float x1,y1,x2,y2;
for(int i=0; i<G->V; i++)
{
for(int k=0; k<G->V;k++)
if(A[i][k]!=maxWT)
printf("%2.3f ",A[i][k]);
else
printf("%5c ",'*');
printf("\n");
};
};
void doDijkstra2(Graph G, int *st, double *wt, int k)
{
int fr[uV];
int v, w, min;
for(v=0;v<G->V;v++)
{
st[v]=-1;
fr[v]=v;
wt[v]=maxWT;
};
st[k]=k;
wt[k]=0;
wt[G->V]=maxWT;
for(min=k;min!=G->V;)
{
v=min;
st[min]=fr[min];
min=G->V;
for(w=0;w<G->V;w++)
if(st[w]==-1)
{
if(wt[v]+G->adj[v][w]<wt[w])
{
wt[w]=wt[v]+G->adj[v][w];
fr[w]=v;
};
if(wt[w]<wt[min]) min=w;
};
};
};
int main()
{
clrscr();
Graph G=NULL;
randomize();
int gd=DETECT,gm=0,st[uV];
double wt[uV+1];
int sign,dec;
while(getche()!=27)
{
clrscr();
if(G)
G=clearGrph(G);
G=randGrph(uV,uE);
outGrph(G);
};
for(int i=0;(getche()!=27)&&(i<uV);i++)
{
doDijkstra2(G,st,wt,i);
printf("%d\n",i);
for(int j=0;j<G->V;j++)
{
gotoxy(2,j+10);
printf("%d. %3.2e (through %d)\n",j+1,wt[j],st[j]+1);
};
};
G=clearGrph(G);
return 0;
};
Соседние файлы в предмете Программирование