弗洛伊德算法C语言实现

#ifndef GUIDE_H_INCLUDED
#define GUIDE_H_INCLUDED
#define MX 1000          //最大值 无穷
#define NUM  17             //最大顶点个数
typedef int adjmatrix[NUM][NUM];
typedef int path[NUM][NUM][NUM];
const int vexs[NUM] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};
int arcs[NUM][NUM] = {
    {0 ,20,MX,MX,20,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX},
    {20,0 ,30,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX},
    {MX,30,0 ,20,MX,30,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX},
    {MX,MX,20,0 ,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX},
    {20,MX,MX,MX,0 ,10,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX},
    {MX,MX,30,MX,10,0 ,20,50,MX,MX,MX,MX,MX,MX,MX,MX,MX},
    {MX,MX,MX,MX,MX,20,0 ,40,10,MX,MX,MX,MX,MX,MX,MX,MX},
    {MX,MX,MX,MX,MX,50,40,0 ,MX,20,20,MX,MX,MX,MX,MX,MX},
    {MX,MX,MX,MX,MX,MX,10,MX,0 ,20,MX,MX,MX,30,MX,MX,MX},
    {MX,MX,MX,MX,MX,MX,MX,20,20,0 ,20,MX,MX,MX,MX,MX,MX},
    {MX,MX,MX,MX,MX,MX,MX,20,MX,20,0 ,20,MX,MX,MX,MX,MX},
    {MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,20,0 ,10,MX,MX,MX,MX},
    {MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,10,0 ,MX,MX,20,MX},
    {MX,MX,MX,MX,MX,MX,MX,MX,30,MX,MX,MX,MX,0 ,20,MX,MX},
    {MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,20,0 ,20,MX},
    {MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,20,MX,20,0 ,40},
    {MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,MX,40,0 }
    };
#endif

 

#include <iostream>
using namespace std;
#include "guide.h"

//=====================================================
void Floeyd( adjmatrix G, adjmatrix D, path P )
{//利用弗洛伊德算法求图GA中每对顶点间的最短长度，对应存于二维数组A中
    for(int v=0; v<NUM; v++)
        for(int w=0; w<NUM; w++){
            D[v][w]=G[v][w];
            for( int u=0; u<NUM; ++u) P[v][w][u]=0;     //0表示FALSE
            if(D[v][w]<MX){
                P[v][w][v]=1;   P[v][w][w]=1;           //1表示TRUE
            }
        }
    for(int u=0; u<NUM; u++)
        for(int v=0; v<NUM; v++)
            for(int w=0; w<NUM; w++)
                if( D[v][u]+D[u][w]<D[v][w]) {
                    D[v][w] =D[v][u]+D[u][w];
                    for( int i=0; i<NUM; ++i)
                        P[v][w][i]=P[v][u][i];
                }
}

//=====================================================
 void guide( adjmatrix GA, int a, int b ,int judge)     //judge判断，1则为start < end,0则为start > end
 {
     adjmatrix D;       //D[i,j]表示从i到j的最短距离；
     path P;       //P[i,j]表示从i到j的最短路径上j的父节点
     Floeyd( GA, D, P );
     cout << D[a][b] << endl;
     cout << "路径为：";
     if( judge==1 )
     {
         for(int u=a;u<b;u++)
         {
                if(P[a][b][u] == 1){
                    cout << u+1 << "->";
                    a=u;
                }
         }
         cout << b+1 << endl;
     }
     else if( judge==0 )
     {
         int i=0;
         int t[NUM]={0};
         for(int u=a;u<b+1;u++)
         {
                if(P[a][b][u] == 1){
                    t[++i]=u+1;
                    a=u;
                }
         }
         for(; i>1; i--)
         {
             cout << t[i] << "->";
         }
         cout << t[1] << endl;
     }
 }
void ShortestPath()
{
    int start = 5;
    int end = 5;
    cout << "输入出发点和目的地编号 (1~17 空格分隔)" << endl;
    cin >> start >> end;
    if(start>0 && start<18 && end>0 && end<18)
    {
            cout <<"从"<< start;
            cout << "到" << end ;
            cout << "的最短路径长度 ：" ;
        if(start<=end)
            guide( arcs, start-1, end-1 ,1);
        else
            guide( arcs, end-1, start-1 ,0);
    }
    else
        cout << "没有这个地方！" << endl;
}


//============== mian文件 =============

int main()
{
    char choose=0;
    cout << "************************" << endl;
    cout << "    a.x到y的最短路径        " << endl;
    cout << "    b.退出            " << endl;
    cout << "    版本号v1.8        " << endl;
    cout << "************************" << endl;
    cin >> choose;
    while( choose!='b' )
    {
        if( choose=='a' )
        {
            ShortestPath();
            cout << "===========================" << endl;
            cout << "  a.x到y的最短路径 b.退出  " << endl;
            cout << "===========================" << endl;
        }
        else if(choose!='a'||choose!='b')    cout << "输入错误，请重新输入：";
        cin >> choose;
    }
    return 0;
}