首页 > 用户发贴区 > 编程问题提问区 > 【求助】关于c中的最短路径问题
2008
12-03

【求助】关于c中的最短路径问题

我最近要编一个程序,照书上抄了一段程序,可是出现了一个问题,不知道怎么改,望请高人指点。


#include <stdio.h>
#define max 9999 
#define maxvertex 100
typedef char vextype;
typedef float adjtype;


typedef struct
{
 int n;
 vextype vexs[maxvertex];
 adjtype arcs[maxvertex][maxvertex];
}graphmatrix;


typedef struct
{
 vextype vertex;
 adjtype length;
 int prevex;
}path;


path dist[6];


void init(graphmatrix &graph, path dist[])
{
 int i;
 dist[0].length=0;
 dist[0].prevex=0;
 dist[0].vertex=graph.vexs[0];


 graph.arcs[0][0]=1;


 for (i=1;i<graph.n;i++)
 {
  dist[i].length=graph.arcs[0][i];
  dist[i].vertex=graph.vexs[i];
  if (dist[i].length!=max)
   dist[i].prevex=0;
  else dist[i].prevex=-1;
 }
}


void dijkstra(graphmatrix graph, path dist[])
{
 int i,j,minvex;
 adjtype min;
 init(graph,dist);
  for (i=1;i<graph.n;i++)
 {
  min=max;
  minvex=0;
  for (j=1;j<graph.n;j++)
  {
   if(graph.arcs[j][j]==0&&dist[j].length<min)
   {
    min=dist[j].length;
    minvex=j;
   }


   if(minvex==0) break;
   graph.arcs[minvex][minvex]=1;


   for(j=1;j<graph.n;j++)
   {
    if (graph.arcs[j][j]==1) continue;
    if (dist[j].length>dist[minvex].length+graph.arcs[minvex][j])
    {
     dist[j].length=dist[minvex].length+graph.arcs[minvex][j];
     dist[j].prevex=minvex;
    }
   }
  }
 }
}



void initgraph(graphmatrix &graph, int n)      
{
 int i,j;
 for(i=0;i<graph.n;i++)
  for(j=0;j<graph.n;j++)
  graph.arcs[i][j]=(i==j?0:max);
  graph.arcs[0][1]=40;
  graph.arcs[0][2]=5;
  graph.arcs[1][2]=12;
  graph.arcs[1][4]=5;
  graph.arcs[2][0]=18;
  graph.arcs[2][3]=13;
  graph.arcs[3][1]=27;
  graph.arcs[3][4]=32;
  graph.arcs[4][3]=31;
  graph.arcs[5][3]=3;
  graph.arcs[0][4]=46;
 
}


void main()
{
 int i;
 graphmatrix graph;


 initgraph(graph,6);
 dijkstra(graph,dist);
 for (i=0;i<graph.n;i++)
  printf(“(%.0f%d)”,dist[i].length,dist[i].prevex);
}


【求助】关于c中的最短路径问题》有 1 条评论

  1. linder 说:

    第23行void init(graphmatrix &graph, path dist[])去掉&改为

    void init(graphmatrix graph, path dist[])

    同理77行的,也是如此处理。

留下一个回复