Grafy

#include <iostream.h>
#include <conio.h>

const int n=7;

int G[n][n]; // graf
int R[n][n]; // tzw. macierz kierowania ruchem
int a, b;
void initG()
{
for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
        G[i][j]=10000; // nieskonczonosc
}

void initR()
{
for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
        R[i][j]=0; // brak drogi
}

void zeruj(int g[n][n])
{
for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
        g[i][j]=0;
}

void floyd(int g[n][n])
{
for(int k=0;k<n;k++)
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if( g[i][k]+g[k][j]<g[i][j])
        {
         g[i][j]=g[i][k]+g[k][j];
         R[i][j]=k;
        }
}

void droga(int i, int j)
{
int k = R[i][j];
if (k != 0)
 {
  droga(i,k);
  textcolor(15);
  cprintf("%d"); textcolor(14); cprintf("--->");
  droga(k,j);
  }
}



int main()
{
char wybor;
do{
initG();
initR();

G[0][3]=30; G[0][1]=10;
G[1][2]=15; G[1][4]=40;
G[2][3]=5;  G[2][4]=20;
G[4][5]=20; G[4][6]=10;
G[5][6]=5;
G[6][3]=25;


gotoxy(1, 24);
textcolor(0);
textbackground(15);
cprintf(" W - Wszystkie mozliwe drogi |  N - Najmniejsza waga i wierzcholki | Q - Wyjscie");
textbackground(0);
gotoxy(1, 25); printf(": ");
scanf("%c", &wybor);

switch(wybor)
        {
        case 'W':
        case 'w':
                {
                clrscr();
                floyd(G);
                for(int i=0; i<n; i++)
                        for(int j=0; j<n; j++)
                                {
                                if(G[i][j]==10000) cout << i << "  -->  " << j << "[drogi nie ma]\n";
                        else
                                if(i!=j)
                                {
                                cout << i << "  -->  " << j << "="<<G[i][j]<<", droga przez: ";
                                droga(i,j);
                                cout << endl;
                                }
                                }
                break;
                }
        case 'N':
        case 'n':
                {
                clrscr();
                gotoxy(1,1);
                textcolor(14);
                cprintf("Wierzcholek poczatkowy: ");
                scanf("%d", &a);
                cprintf("Wierzcholek koncowy: ");
                scanf("%d", &b);
                textcolor(15);
                if(G[a][b]==10000)
                        {
                        textcolor(12);
                        cprintf("\nBrak bezposredniego polaczenia z ");textcolor(15); cprintf("%d do %d.\n", a, b);
                        }
                floyd(G);
                if(G[a][b]!=10000)
                        {
                        gotoxy(1, 6);
                        printf("---------------------------------------");
                        gotoxy(1, 7);
                        textcolor(15); cprintf("Droga wg. wagi");
                        gotoxy(1, 8);
                        textcolor(14); cprintf("Waga wynosi: ");textcolor(15);cprintf("%d ", G[a][b]);
                        gotoxy(1, 9); textcolor(15);
                        cprintf("%d", a); textcolor(14);cprintf("--->");
                        droga(a, b);
                        textcolor(15);
                        cprintf("%d", b);
                        printf("\n---------------------------------------");
                        }
                break;
                }
        }
getch();
clrscr();
}while(wybor!='q');
}