СиАОД3

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