TJZ_csdn 2016-06-07 05:15 采纳率: 0%
浏览 3105

用Floyd算法求从某地到某地的最短路径(无向图)

#include
#include
using namespace std ;

#define MUNum 20
#define INFINITY 32767
#define Myprintf cout << "\n\t+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-\n" << endl

typedef struct PlaneGraph
{
int PathLength ;
char Pathname[20] ;
}PlaneGraph,PG[MUNum][MUNum] ;

typedef struct
{
char name[20] ;
int num ;
}infor ;

typedef struct
{
infor vexs[MUNum] ;
PG arcs ;
int vexnum ,arcnum ;
}AMGraph ;

void InitGraph(AMGraph &G)
{
int i ,j ;
cout << "\t请输入校园地点的数量、校园小径的个数:" ;
cin >> G.vexnum >> G.arcnum ;//点 边
Myprintf ;

for(i=0 ;i<G.vexnum ;i++)
    G.vexs[i].num = i ;//为点进行编号

cout << " 输入编号为(0-" << i << ")的校园地点的名称:\n\n" ;//店名称
for(i=0 ;i<G.vexnum ;i++)
{
    cout << "\t" ;
    cin  >> G.vexs[i].name ; 
}

cout << endl ;
Myprintf ;

for(i=0 ;i<G.vexnum ;i++)
    for(j=0 ;j<G.vexnum ;j++)
    {
        G.arcs[i][j].PathLength = INFINITY ; 
        strcpy(G.arcs[i][j].Pathname,"null");
    }

//输入路径信息
int v1,v2,w ;
char wn[20] ;
cout << "输入校园小径首尾地点编号、小径长度及小径名称\n\t(以-1 -1 -1 -1)结束输入:\n\t" << endl ;
cin  >> v1 >> v2 >> w >> wn ;
while(v1!=-1 && v2!=-1 && w!=-1 && strcmp(wn,"-1")!=0)
{
    cout << "\t" ;
    G.arcs[v1][v2].PathLength = w ;
    strcpy(G.arcs[v1][v2].Pathname,wn);
    G.arcs[v2][v1].PathLength = w ;
    strcpy(G.arcs[v2][v1].Pathname,wn);
    cin >> v1 >> v2 >> w >> wn ;
}

Myprintf ;

}

//Floyd
void ShortestPath(AMGraph G)
{
int v,u,i,j,w,k,flag=1;
int p[MUNum][MUNum][MUNum],D[MUNum][MUNum];
for(v=0 ; v for(w=0 ;w {
D[v][w] = G.arcs[v][w].PathLength;
for(u=0;u p[v][w][u] = 0 ;//
if(D[v][w] p[v][w][v] = p[v][w][w] = 1;//
}
for(u=0 ;u for(v=0 ;v for(w=0 ;w if(D[v][u]+D[u][w] {
D[v][w] = D[v][u]+D[u][w];
for(i=0;i p[v][w][i] = p[v][u][i] || p[u][w][i];//
}
while(flag)
{
cout cin >> k >> j ;
if(k=G.vexnum || j=G.vexnum )
{
cout << "该地点不存在!请重新输入!" << endl ;
Myprintf ;
}
else if(k == j )
{
cout << "始点和终点相同!请重新输入!" << endl ;

Myprintf ;
}
else
flag = 0 ;
}

    //输出信息
    int L[MUNum];
    L[0] = k;
    int l = 1 ;

    cout << "\t总路线长:" << D[k][j] << endl ;

    cout << G.vexs[k].name ;
    for(u=0 ;u<G.vexnum ;u++)
        if(p[k][j][u] && k!=u && j!=u)
        {
            cout << " ——> " << G.vexs[u].name ;
            L[l] = u ;
            l++ ;
        }   

    cout << " ——> " << G.vexs[j].name ;
    L[l] = j ;
    cout << endl ;

    cout << "\t路线:" ;
    for(u=0 ;u<l ;u++)
    {
        cout << G.arcs[L[u]] [L[u+1]].Pathname ;
        if(u != l-1)
            cout << " ——> " ;
    }
    cout << endl ;
    Myprintf ;

}

int main()
{
cout << "\n----------------------------------校园导航----------------------------------" << endl << endl ;
AMGraph G ;
InitGraph(G) ;
char k[10] ;
strcpy(k,"Yes");
while(strcmp(k,"Yes")==0)
{
ShortestPath(G);
cout << "请问是否继续?Yes or No?" << endl ;
cin >> k ;
if(strcmp(k,"Yes") != 0 )
cout << "\n----------------------------------停止查询----------------------------------" << endl ;
}
return 0 ;
}

数据:

10 10

大学生活动中心

敬文图书馆
实验楼
行知楼
防空洞
宿舍楼
办公楼
外国语学院
美术学院
体育馆

0 1 10 逸夫路
1 3 15 敬文路
4 3 70 达夫路
1 2 20 朝阳路
3 7 77 富康路
4 5 12 人民路
5 6 19 孚玉路
6 7 56 龙门路
8 9 73 纬七路
8 7 8 九江路
-1 -1 -1 -1

在路线输入:1 9 和 9 1的时候路线不一样,请问怎么解决

  • 写回答

2条回答

  • Robot-C 2016-06-07 05:22
    关注

    http://blog.csdn.net/hackerain/article/details/6055946
    #define MAX_VERTEX_NUM 20
    #define MAX 1000000000
    typedef struct
    {
    std::string vexs[MAX_VERTEX_NUM];
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];......
    答案就在这里:Floyd算法求最短路径
    ----------------------你好,人类,我是来自CSDN星球的问答机器人小C,以上是依据我对问题的理解给出的答案,如果解决了你的问题,望采纳。

    评论

报告相同问题?

悬赏问题

  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常
  • ¥15 关于风控系统,如何去选择
  • ¥15 这款软件是什么?需要能满足我的需求
  • ¥15 SpringSecurityOauth2登陆前后request不一致