| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 518 人关注过本帖
标题:求助求助。。帮忙帮忙。。拓扑问题。。最短路由路径
只看楼主 加入收藏
sujulee
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2011-9-20
结帖率:0
收藏
已结贴  问题点数:10 回复次数:2 
求助求助。。帮忙帮忙。。拓扑问题。。最短路由路径
#include "string.h"
#include "stdio.h"
#define INFINITY    9999
#define MAX_VERTEX_NUM    11
#define TRUE    1
#define FALSE   0
typedef struct{
    char vex[MAX_VERTEX_NUM][5];
    int  arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int  vexnum;

}MGraph;
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{
    int i,j,v,w,min,final[MAX_VERTEX_NUM];
    for(v=0;v<G.vexnum;++v)
    {
        final[v]=FALSE; D[v]=G.arcs[v0][v];
        for(w=0;w<G.vexnum;++w)  P[v][w]=FALSE;
        if(D[v]<INFINITY)  {P[v][v0]=TRUE; P[v][v]=TRUE;}
    }
    D[v0]=0;  final[v0] =TRUE;
    for(i=1;i<G.vexnum;++i)
    {
        min=INFINITY;
        for(w=0;w<G.vexnum;++w)
            if(!final[w])
                if(D[w]<min)  {v=w;min=D[w];}
        final[v]=TRUE;
        for(w=0;w<G.vexnum;++w)
            if(!final[w]&&(min+G.arcs[v][w]<D[w]))
            {
                D[w]=min+G.arcs[v][w];
                for(j=0;j<MAX_VERTEX_NUM;j++)
                    P[w][j]=P[v][j];
                P[w][w]=TRUE;
            }
    }
}

void main()
{
    int v0=0,i,j,n;
    MGraph G={"R1","R2","R3","R4","R5","R6","N1","N2","N3","N4","N5",
    0,9999,9999,8,9999,9999,5,9999,9999,9999,9999,
   9999,0,9999,9999,4,9999,7,9999,9999,9999,9999,
   9999,9999,0,9999,9999,9999,3,2,9999,9999,9999,
   8,9999,9999,0,9999,9999,9999,9999,2,9999,9999,
   9999,4,9999,9999,0,9999,9999,9999,5,2,9999,
   9999,9999,9999,9999,9999,0,9999,9999,9,9999,5,
   0,0,0,9999,9999,9999,0,9999,9999,9999,9999,
   9999,9999,0,9999,9999,9999,9999,0,9999,9999,9999,
   9999,9999,9999,0,0,0,9999,9999,0,9999,9999,
   9999,9999,9999,9999,0,9999,9999,9999,9999,0,9999,
   9999,9999,9999,9999,9999,0,9999,9999,9999,9999,0,
    MAX_VERTEX_NUM };
    PathMatrix  P;
    ShortPathTable  D;
    ShortestPath_DIJ(G,v0,P,D);
    printf("开始路由器    目的路由器或目的网络     经过的路由器或网络序列     最短路径值\n");
    for(i=1;i<MAX_VERTEX_NUM;i++)
    {
        printf("     %s               %s                ",G.vex[v0],G.vex[i]);
        for(j=0,n=0;j<MAX_VERTEX_NUM;j++)
            if(P[i][j])            //显示经过路径
            {    printf(" %s ",G.vex[j]); n++;  }
        for(j=0;j<8-n;j++)   //对齐
            printf("    ");
        printf("%d\n",D[i]);
    }
printf("目的网络                        下一跳(路由器)\n");
    for(i=6;i<MAX_VERTEX_NUM;i++)
    {
        printf("%s                       ",G.vex[i]);
        for(j=1;j<6;j++)
        {
            if(P[i][j]&&G.arcs[i][j]<9999)
                printf("            %s",G.vex[j]);
            }
        printf("\n");
    }
    }
这个程序怎么判断输入是否符合拓扑要求。。。求修改、、、谢谢啦。。。。
搜索更多相关主题的帖子: 路由 include 
2011-09-21 15:21
无名可用
Rank: 4
等 级:业余侠客
帖 子:79
专家分:259
注 册:2010-7-27
收藏
得分:10 
看了你上一个帖子,汗,不就是DIJKSTRA算法求单源最短路,建议看看算法导论,里面算法讲的很清楚
如果优先队列不懂的话可以不用,笨方法实现也可以,数据量不是很大的话时间还是过得去
2011-09-22 09:40
sujulee
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2011-9-20
收藏
得分:0 
我看了。。看不懂。。是因为编程实验我抽到了这道题。。有要求就是用拓扑图输入。。那个我一点都不会
2011-09-22 14:35
快速回复:求助求助。。帮忙帮忙。。拓扑问题。。最短路由路径
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026082 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved