数据结构:图-最短路径-Dijkstra算法-创新互联

#define MAXSIZE 100
#define MAXLEN 10
#include#include#define MAXCOST 1000
#define MAX 100
typedef struct vertex
{
    int num;
}DataType;

typedef struct
{
    DataType vexs[MAXLEN+1];
    int edges[MAXLEN+1][MAXLEN+1];
    int n,e;
}MGraph;

void createcost( MGraph *g,int n,int e )
{
   int i,j,k,v1,v2;
   int weight;
   g->n=n;
   g->e=e;
   for(i=1;i<=g->n;i++)
    {
       g->vexs[i].num=i;
    }
   for(i=1;i<=g->n;i++)
      for(j=1;j<=g->n;j++)
    {
      g->edges[i][j]=MAXCOST;
    }
   for(k=1;k<=g->e;k++)
    {
   scanf("%d,%d,%d",&v1,&v2,&weight);
   g->edges[v1][v2]=weight;
    }
}
void Dijkstra(MGraph g,int v)
{ 
    int dist[MAXLEN+1];
	int path[MAXLEN+1];
    int s[MAXLEN+1];
    int min,i,j,w,k;
    for(i=1;i<=g.n;i++)
    { 
	  dist[i]=g.edges[v][i];
      if(i==v) s[i]=1; 
	  else     s[i]=0;
      path[i]=-1;
      if(dist[i]%d无最短路径!\n",v,i);
       else
        { 
	       printf("%d--->%d: length=%d\n",v,i,dist[i]); 
           printf("path: ");
           j=i;
           while(path[j]!=v) 
            { 
		    printf("%d-",path[j]);
            j=path[j];
            }
            printf("%d\n",path[j]);
        }
    } 
}

int main()
{
    MGraph x;
    int peak;
    int side;
    printf("请输入顶点数和边数:");
    scanf("%d%d",&peak,&side);
    printf("请输入邻接矩阵:(测试数据)\n");
    createcost(&x,peak,side);
    Dijkstra(x,1);
    return 0;
}

测试数据:
1,2,40
1,3,10
1,5,45
2,5,10
2,3,15
3,1,20
3,4,15
4,2,20
4,5,35
6,4,3

成都创新互联公司-专业网站定制、快速模板网站建设、高性价比蓬安网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式蓬安网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖蓬安地区。费用合理售后完善,十年实体公司更值得信赖。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网页标题:数据结构:图-最短路径-Dijkstra算法-创新互联
路径分享:http://myzitong.com/article/pchgh.html