Đề bài: Đồ thị vô hướng G={V,E} có trọng sôd Cho u, v thuộc V. Xây dựng thuật toán tìm hai đường đi a(u,v) và b(u,v) sao cho không có cạnh nào chung và có tổng độ dài ngắn nhất.
Đây là 1 đoạn code giải thuật Floyd em tìm được trên diễn đàn. Các anh chị có thể giúp e dựa vào đó để tìm đường đi ngắn thứ 2 mà không trùng với đường đi ngắn nhât trước đó không ạ.
Ý tưởng của e là xóa các cạnh đã đi(đưa về vô cùng) và duyệt lại đồ thị lần nữa. Nhưng e vẫn k biết viết code ra sao cả.HIC


Mã:
#include<stdio.h>#include<conio.h> #define TOIDA 50#define VOCUNG 30000#define TRUE 1#define FALSE 0 /* Khai bao ma tran trong so cua do thi   weight[i][j] = 0       : neu i = j   weight[i][j] = VOCUNG  : neu tren do thi khong co cung <i ,j>   weight[i][j] != 0      : tren do thi co cung <i,j>*/ int weight[TOIDA][TOIDA]; // Ma tran D[][]:ma tran cho biet chieu dai ngan nhat di tu nut x den nut y  int D[TOIDA][TOIDA]; /* Ma tran P[][]: ma tran cho biet duong di ngan nhat tu nut x den nut y co qua nut trung gian  P[x][y] hay khong:      * Neu P[x][y] == -1: duong di ngan nhat tu nut x den nut y khong qua nut trung gian.      * Neu P[x][y] != -1: duong di ngan nhat tu nut x den nut y co di qua nut trung gian P[x][y].*/ int P[TOIDA][TOIDA]; int SoNut; // Tac vu initialize: khoi dong ma tran trong so cua do thi  void initialize(){     int i,j;     for(i=0;i<TOIDA;i++)               for(j=0;j<TOIDA;j++)               {                                   if(i==j) weight[i][j]=0;                                   else     weight[i][j]=VOCUNG;               }}; // Tao mot cung tu node1 den node2 voi trong so wt  void joinwt(int node1,int node2,int wt){     if(node1 != node2) weight[node1][node2]=wt;}; // Xoa cung tu node1 den node2 tren dot hi co trong so void remvwt(int node1,int node2){     if(node1 != node2) weight[node1][node2]=VOCUNG;}; /* Tac vu foyd: tim duong di ngan nhat tren do thi co trong so, tac vu nay tinh qua hai ma tran D[][] va p[][];      - Ma tran D[][]: ma tran cho biet chieu dai ngan nhat di tu nut x den nut y.      - Ma tran P[][]: ma tran cho biet duong di ngan nhat tu nut x den nut y co qua nut trung gian P[x][y] hay khong:           * Neu P[x][y] == -1: duong di ngan nhat tu nut x den nut y khong qua nut trung gian.           * Neu p[x][y] != -1: duong di ngan nhat tu nut x den nut y co di qua nut trung gian P[x][y].*/ void floyd(){     int i,j,k;          //khoi dong ma tran D va P          for(i=0;i<SoNut;i++)                for(j=0;j<SoNut;j++)                {                                    D[i][j] = weight[i][j];                                             P[i][j] = -1;                }          // Tinh ma tran D va P o buoc lap thu k          for(k = 0;k < SoNut;k++)                for(i = 0;i < SoNut;i++)                             if( (D[i][k] > 0) && (D[i][k] < VOCUNG) )                          for(j = 0;j < SoNut;j++)                                if( (D[k][j] > 0) && (D[k][j] < VOCUNG) )                                    if( (D[i][j] != 0) && (D[i][k]+D[k][j] < D[i][j]) )                                    {                                                 D[i][j] = D[i][k]+D[k][j];                                                 P[i][j] = k;                                    }                };                                         // In lo trinh ngan nhat.     void inlotrinh(int x,int y)     {          int r;          if(P[x][y] == -1)          {                     printf(" %d -> %d ",x,y);                     return;          }          else          {                     r = P[x][y];                     inlotrinh(x,r);                     inlotrinh(r,y);          }     };          // Chuong trinh chinh.     int main()     {          int i,j,chucnang,x,y,trongso,themcung,xoacung;          char c;          int p,q,r;//          clrscr();          initialize();  //khoi dong do thi.          SoNut = 0;          do          {                // Menu chinh cua chuong trinh                printf("

\t\t GIAI THUAT FLOYD TIM DUONG DI NGAN NHAT");                printf("

 Cac chuc nang chinh cua chuong trinh:
");                printf("1: tao do thi moi
");                printf("2: them mot nut
");                printf("3: them cung
");                printf("4: xoa mot cung
");                printf("5: xoa toan bo do thi
");                printf("6: xac dinh so nut co tren do thi
");                printf("7: duyet cac cung
");                printf("8: tim cung
");                printf("9: tim duong di ngan nhat (giai thuat FLOYD)
");                printf("0: ket thuc chuong trinh
");                printf("Chuc nang ban chon: ");                scanf("%d", &chucnang);                switch(chucnang)                {                                case 1:                                       {                                            initialize();                                            SoNut = 0;                                            printf("
Do thi moi co bao nhieu nut: ");                                            scanf("%d",&SoNut);                                            printf("Hay nhap so nut cua do thi ( nhap %d %d de ket thuc ) :
",SoNut,SoNut);                                            x = 0;                                            y = 0;                                            while(x < SoNut && y < SoNut )                                            {                                                    printf(" Nhap cung: ");                                                    scanf("%d%d",&x,&y);                                                    while(x >= SoNut || y >= SoNut || x == y)                                                    {                                                            if(x == SoNut && y == SoNut) break;                                                            printf(" Nhap khong hop le");                                                            printf("
 Nhap lai: ");                                                            scanf("%d%d",&x,&y);                                                    }                                                    if( x != SoNut && y != SoNut && x != y)                                                    {                                                            printf(" Trong so cua cung %d -> %d la: ",x,y);                                                            scanf("%d",&trongso);                                                            joinwt(x,y,trongso);                                                    }                                            };                                            break;                                       }                                case 2:                                         {                                            if(SoNut<TOIDA)                                            {                                                           SoNut++;                                                    printf("So nut hien co la %d",SoNut);                                            }                                            else    printf("khong the them nut moi");                                            break;                                        }                                case 3:                                         {                                            printf("
Nhap so cung can them(neu ban khong muon tiep tuc them cung nhap %d %d : ",x,y);                                            scanf("%d",&themcung);                                            for(int n = 0;n < themcung;n++)                                            {                                                    printf("Nhap cung: ");                                                    scanf("%d%d",&x,&y);                                                    if(x == SoNut && y == SoNut) break;                                                    while(weight[x][y] != VOCUNG || x >= SoNut || y >= SoNut || x == y)                                                    {                                                               printf(" Nhap khong hop le hoac cung da co");                                                          printf("
 Nhap lai: ");                                                          scanf("%d%d",&x,&y);                                                    }                                                                                                       printf(" Trong so cua cung %d -> %d la: ",x,y);                                                    scanf("%d",&trongso);                                                    joinwt(x,y,trongso);                                            }                                            break;                                        }                                case 4:                                         {                                            printf("
Nhap so cung can xoa (neu ban khong muon tiep tuc xoa nhap %d %d : ",x,y);                                            scanf("%d",&xoacung);                                            for(int n = 0;n < xoacung;n++)                                            {                                                    printf("Nhap cung: ");                                                    scanf("%d%d",&x,&y);                                                    if(x == SoNut && y == SoNut) break;                                                    while(weight[x][y] == 0 || weight[x][y] == VOCUNG || x >= SoNut || x >= SoNut)                                                    {                                                                  printf("Khong co cung nay");                                                           printf("
Nhap lai: ");                                                           scanf("%d%d",&x,&y);                                                    }                                                    remvwt(x,y);                                            }                                        }                                case 5:                                        {                                            printf("
Ban co chac khong (c/k): ");                                            c=getche();                                            if(c=='c' || c=='C')                                            {                                                      initialize();                                                      SoNut = 0;                                            }                                            break;                                        }                                case 6:                                        {                                            printf("
So nut co tren do thi la %d",SoNut);                                            break;                                        }                                case 7:                                         {                                            printf("\Cac cung co tren do thi:
 ");                                            for(i=0;i<SoNut;i++)                                                 for(j=0;j<SoNut;j++)                                                       if( (weight[i][j]>0) && (weight[i][j]<VOCUNG) )                                                            printf("%d%s%d: %d
",i," -> ",j,weight[i][j]);                                            break;                                        }                                case 8:                                        {                                            printf("\Nhap cung can tim: ");                                            scanf("%d%d",&x,&y);                                            if(x >= SoNut || y >= SoNut)                                                 printf("khong hop le");                                            else                                            {                                                 if( (weight[x][y]>0) && (weight[x][y]<VOCUNG) )                                                     printf("Cung co trong so %d",weight[x][y]);                                                 else                                                     printf("khong co cung nay");                                            }                                            break;                                        }                                case 9:                                         {                                            printf("
Nhap nut di va nut den: ");                                            scanf("%d%d",&x,&y);                                            if(x >= SoNut || y >= SoNut)                                                 printf("khong hop le");                                            else                                            {                                                 floyd();                                                 printf("Chieu dai ngan nhat du %d -> %d la %d",x,y,D[x][y]);                                                 printf("
Duong di la: ");                                                 inlotrinh(x,y);                                            }                                            break;                                        }                }          }while(chucnang!=0);     getch();     return 0;}
[/QUOTE]