| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 571 人关注过本帖
标题:迪杰斯特拉算法求最短路径
只看楼主 加入收藏
xie2010
Rank: 2
来 自:广东
等 级:论坛游民
帖 子:5
专家分:10
注 册:2010-10-27
结帖率:0
收藏
已结贴  问题点数:10 回复次数:2 
迪杰斯特拉算法求最短路径
有没有人能帮忙解释一下这个程序啊,里面很多变量都不知道是什么意思。谢谢。

//定义常量和使用二维数组存储网
#include <stdio.h>
#define MAX 100      //表示两者之间的距离为无穷大

typedef int path[11][11],dist[11];
typedef int MGraph[11][11];
int q[11];
                // R1, R2, R3, R4, R5, R6, N1, N2, N3, N4, N5
int arcs[11][11]={  0,MAX,MAX,  8,MAX,MAX,  5,MAX,MAX,MAX,MAX,  //R1
                  MAX,  0,MAX,MAX,  4,MAX,  7,MAX,MAX,MAX,MAX,  //R2
                  MAX,MAX,  0,MAX,MAX,MAX,  3,  2,MAX,MAX,MAX,  //R3
                    8,MAX,MAX,  0,MAX,MAX,MAX,MAX,  2,MAX,MAX,  //R4
                  MAX,  4,MAX,MAX,  0,MAX,MAX,MAX,  5,  2,MAX,  //R5
                  MAX,MAX,MAX,MAX,MAX,  0,MAX,MAX,  9,MAX,  5,  //R6
                    0,  0,  0,MAX,MAX,MAX,  0,MAX,MAX,MAX,MAX,  //N1
                  MAX,MAX,  0,MAX,MAX,MAX,MAX,  0,MAX,MAX,MAX,  //N2
                  MAX,MAX,MAX,  0,  0,  0,MAX,MAX,  0,MAX,MAX,  //N3
                  MAX,MAX,MAX,MAX,  0,MAX,MAX,MAX,MAX,  0,MAX,  //N4
                  MAX,MAX,MAX,MAX,MAX,  0,MAX,MAX,MAX,MAX,  0}; //N5

//使用Dijkstra算法求R1到其它节点的最短路径
void ShortestPath(MGraph arc,int v0,path &P,dist &D)
{
    int i,j,v,w,min;
    int final[11];
    for (v=0;v<11;++v)
    {
        final[v] = 0;
        D[v]=arcs[v0][v];     //距离distance
        for (w=0; w<11; ++w)  
            P[v][w] = 0;      //路径path
        if (D[v] <MAX)
        {
            P[v][v0] = 1;
            P[v][v] = 1;
        }
    }
    D[v0] = 0;
    final[v0] = 1;
    for (i=1; i<11; ++i)
    {         
        min = MAX;
        for (w=0; w<11; ++w)
            if (!final[w])
                if (D[w]<min)
                {
                    v=w;
                    min=D[w];
                }
        final[v] = 1;
        for (w=0; w<11; ++w)
            if (!final[w] && (min+arcs[v][w]<D[w]))
                {
                    D[w] = min + arcs[v][w];
                    q[w]=v;
                    for(j=0;j<11;j++)
                        P[w][j] = P[v][j];
                    P[w][w] = 1;
                }
    }
}

//主函数和打印最短路径和路由表
void main()
{
    path p;
    dist d;
    int v0=0;
    int i,j=0,r=22, a, b,temp=0, s1=5,arcs1[6][11];
    char str[22]={'R','1','R','2','R','3','R','4','R','5','R','6','N','1','N','2','N','3','N','4','N','5'};
   
    for (i=0;i<11;i++)
        q[i]=v0;
    for(i=0;i<6;i++)
        for(j=0;j<11;j++)
            arcs1[i][j]=MAX;
        
        ShortestPath(arcs,v0,p,d);
        
        for(i=6;i<11;i++)
        {
            a=q[i];
            arcs1[i-6][10]=i;
            for(j=9;j>0;j--)
            {
                if(a!=v0)
                {
                    arcs1[i-6][j]=a;
                    a=q[a];
                }
                if(arcs1[i-6][j]==v0)
                    break;
            }
        }
        printf ("\n路由器\t网络\t最短路径经过的路由器或网络\t最短路径值\n");
        
        for(i=6;i<11;i++)
        {
            printf("  %c%c\t %c%c\t%c%c", str[v0*2], str[v0*2+1], str[2*i], str[2*i+1], str[v0*2], str[v0*2+1]);
            for(j=0;j<11;j++)
            {
                if(arcs1[i-6][j]!=MAX&&arcs1[i-6][j]!=v0)
                {
                    a=2*arcs1[i-6][j];
                    b=2*arcs1[i-6][j]+1;
                    printf("-%c%c",str[a],str[b]);
                }   
            }
            printf("\t\t\t\t%d\n",d[i]);
        }
        printf("\t\t网络\t下一路由器 \n");
        for(i=6;i<11;i++)
        {
            printf("\t\t%c%c       ",str[2*i],str[2*i+1]);
            for(j=0;j<11;j++)
            {
                if(arcs1[i-6][j]!=MAX&&arcs1[i-6][j]!=v0&&arcs1[i-6][j]<6)
                {
                    a=2*arcs1[i-6][j];
                    b=2*arcs1[i-6][j]+1;
                    printf("\t%c%c\n",str[a],str[b]);
                    temp=1;
                    break;
                }   
            }
            
            if(!temp)
                printf("\t--\n");
        }
}
搜索更多相关主题的帖子: include 
2011-12-07 23:22
jj369258
Rank: 4
等 级:业余侠客
帖 子:116
专家分:226
注 册:2010-12-2
收藏
得分:10 
看不懂!路过,表示来学习的!
2011-12-08 15:40
xie2010
Rank: 2
来 自:广东
等 级:论坛游民
帖 子:5
专家分:10
注 册:2010-10-27
收藏
得分:0 
没人回答,悲剧啊~
2011-12-19 22:01
快速回复:迪杰斯特拉算法求最短路径
数据加载中...
 
   



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

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