注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

小人物的自述

为梦想而奋斗,没有梦想就没有希望!

 
 
 

日志

 
 

一个数据结构里的最短路经问题  

2006-04-24 22:35:27|  分类: 学习笔记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

#include "stdio.h"

#define MAXVERTICES 6     
#define MaxVertexNum 6
#define infinity 1000


typedef struct Gragh{
      int vexs[MaxVertexNum];
      int edges[MaxVertexNum][MaxVertexNum];
      int n,e;
}Graphic;

void CreateMGraph(Graphic *G)
{
    int i,j,k,w,temp;
   printf("write num of node & border");
      scanf("%d%d",&G->n,&G->e);
   printf("write information of node");
      for(i=0;i<G->n;i++)
   {
    scanf("%d",&temp);
    G->vexs[i]=temp;
   }
      for(i=0;i<G->n;i++)
         for(j=0;j<G->n;j++)
            G->edges[i][j]=infinity;
      for(k=0;k<G->e;k++)
   {
    printf("write (vi,vj) and weight");
         scanf("%d%d%d",&i,&j,&w);
         G->edges[i][j]=w;
       }
}


void shortestpath(Graphic g,int v0,int d[],int p[][MaxVertexNum])
{
 int v,w,i,j,min,final[MaxVertexNum];
 for(v=0;v<g.n;++v)
 {
  final[v]=0;
  d[v]=g.edges[v0][v];
  for(w=0;w<g.n;++w)
   p[v][w]=0;
  if(d[v]<infinity)
  {
   p[v][v0]=1;
   p[v][v]=1;
  }
 }
 d[v0]=0;final[v0]=1;
 for(i=1;i<g.n;++i)
 {
  min=infinity;
  for(w=0;w<g.n;++w)
   if(!final[w])
    if(d[w]<min)
    {
     v=w;
     min=d[w];
    }
  final[v]=1;
  for(w=0;w<g.n;++w)
   if(!final[w]&&(min+g.edges[v][w]<d[w]))
   {
    d[w]=min+g.edges[v][w];
    for(j=0;j<g.n;j++)
     p[w][j]=p[v][j];  
    p[w][w]=1;
    p[w][v]=1;
   }
 }
 for(i=0;i<g.n;i++)
 {
  printf("vo to v%d's road is:",i);
  for(j=0;j<g.n;j++)
   if(p[i][j]==1)
   printf("%d\t",j);
  printf("\n");
 }
}


void putout(Graphic G,int distance[])
{
 int j;
 for(j=0;j<G.n;j++)
  printf("%d\n",distance[j]);
}

void main()
{
 Graphic Create;
 int cost[MAXVERTICES][MAXVERTICES];
 int distance[MAXVERTICES];
 int found[MAXVERTICES];
 int v=0;
 int c,c1;
 int p[MaxVertexNum][MaxVertexNum];
 CreateMGraph(&Create);
 for(c=0;c<MAXVERTICES;c++)
  for(c1=0;c1<MAXVERTICES;c1++)
   cost[c][c1]=Create.edges[c][c1];
 shortestpath(Create,v,distance,p);
 putout(Create,distance);
}

如有什么问题请留言,我们一起探讨一下!网上的东西总是乱七八糟的看不懂自己就写了一个,希望对别人有些帮助!

  评论这张
 
阅读(45)| 评论(0)
推荐

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017