| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 565 人关注过本帖
标题:一个关于图生成和迪杰斯特拉算法的问题,搞了好久,还是不懂哪里有问题,求 ...
只看楼主 加入收藏
任重道远
Rank: 1
等 级:新手上路
帖 子:57
专家分:7
注 册:2015-9-12
结帖率:66.67%
收藏
 问题点数:0 回复次数:2 
一个关于图生成和迪杰斯特拉算法的问题,搞了好久,还是不懂哪里有问题,求大神看看
一个作业:求顶点数为500、1000、1500等等时,用迪杰斯特拉算法求的最短路径的时间,其中权值随机生成。
如题
 #include <stdio.h>
 #include <stdlib.h>                          //这是相关的代码
 #include <time.h>                          //我有几个问题:
 #include <stdbool.h>                      //第一个:在用邻接矩阵存储图时,初始化图的边的信息之后,
                                         //要给图中存在的边赋给一个随机的权值,怎么弄?(即代码中的红色部分)。
 #define MAX 999999                    //第二个:程序可以运行,但为什么当VEX_NUM的值不变时每次输出的结果不同
 #define VEX_NUM 600                 //有时是5毫秒、有时是10毫秒、后来干脆是0毫秒???
                                    //第三个:当VEX_NUM比较大时(如1000)会发生内存错误,那是不是说明这道
 typedef struct                    //题不能用这样的方法来解决?
 {                               //另外,后面的两个问题是不是因为第一个问题造成的?怎么解决啊?
     int vex[VEX_NUM];         //求帮助啊   
     int edgeifo[VEX_NUM][VEX_NUM];
     int vexnum,edgenum;
 }Graph;
 
void creategraph(Graph *G,int n,int e);
 void Dijkstra(Graph *G,int v);
 
int main(void)
 {
     clock_t start,end;
     Graph G;
 
    start=clock();
 
    creategraph(&G,600,599);
     Dijkstra(&G,0);
 
    end=clock();
 
    printf("运行时间为%d毫秒。\n",end-start);
     system("pause");
     return 0;
 }
 /*用邻接矩阵的方式构造图*/
 void creategraph(Graph *G,int n,int e)
 {
     int i,j,k;
     G->vexnum=n;
     G->edgenum=e;
 
    for(i=0;i<n;i++)
     {
         G->vex[i]=i;
     }
 
    for(i=0;i<n;i++)
     {
         for(j=0;j<n;j++)
             G->edgeifo[i][j]=MAX;     //初始化
     }

/*    for(k=0;k<e;k++)
     {
         ???
     }
 */

 }
 
void Dijkstra(Graph *G,int v)
 {
     bool S[VEX_NUM];
     int n=VEX_NUM;
     int dist[VEX_NUM];
     int prev[VEX_NUM];
     int i,j,k,mindist;
 
    for(i=0;i<n;i++)
     {
         dist[i]=G->edgeifo[v][i];
         S[i]=false;
         if(dist[i]==MAX)
             prev[i]=-1;
         else
             prev[i]=v;
     }
     dist[v]=0;
     S[v]=true;
 
    for(i=1;i<n;i++)
     {
         mindist=MAX;
         k=v;
         for(j=0;j<n;j++)
         {
             if((!S[j])&&dist[j]<mindist)
             {
                 k=j;
                 mindist=dist[j];
             }
             S[k]=true;
         }
         for(j=0;j<n;j++)
         {
             if((!S[j])&&G->edgeifo[k][j]<MAX)
             {
                 if(dist[k]+G->edgeifo[k][j]<dist[j])
                 {
                     dist[j]=dist[k]+G->edgeifo[k][j];
                     prev[j]=k;
                 }
             }
         }
     }
 }
 

[ 本帖最后由 任重道远 于 2015-10-3 12:26 编辑 ]
搜索更多相关主题的帖子: 信息 include 
2015-10-02 16:19
qq1625127317
Rank: 6Rank: 6
等 级:侠之大者
威 望:1
帖 子:185
专家分:450
注 册:2015-9-3
收藏
得分:0 
不太清楚。。。。。

静坐常思己过,闲谈莫论人非
2015-10-08 13:20
诸葛欧阳
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:流年
等 级:贵宾
威 望:82
帖 子:2790
专家分:14619
注 册:2014-10-16
收藏
得分:0 
没听说过这个算法,不过我想问一下你是存储像素信息还是什么?

一片落叶掉进了回忆的流年。
2015-10-08 14:08
快速回复:一个关于图生成和迪杰斯特拉算法的问题,搞了好久,还是不懂哪里有问题 ...
数据加载中...
 
   



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

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