Question

数据结构算法设计题，会的进来看看

设计一个算法,求图G中距离顶点V的最短路径长度最大的一个顶点,设V可达其余各个顶（最好有完整答案，本人小白）

Answer 1

迪杰斯特拉算法   data 数组里存放的是 有向图的 矩阵表示

QQ   578721802

#include "stdio.h"
#include "stdlib.h"
#define INT_MAX 32676
/**
 Dijkstra 算法是用来计算图中一个
          顶点到 其余的所有顶点的
          最短距离的算法
*/
/***
     -1 表示两点之间距离是无限大
     path[v] 表示的这个数组代表了Vx到 v 的最短路径
     路径 = path[v][0],v,path[v][1],path[v][2] 直到一个path[v][x] == -1

     Length[v] 代表了Vx到 v 的最短长度：权之和

     代码注释:


**/
typedef struct graph{
    int **p;
    int vertNum;
    int arcNum;
}*Graph,g;
typedef struct l{
   int* le;
   bool* isIn;
}*Le;
int VETNUM=6;
void init(Le &L,int **&P,Graph &G);
void Dijikstra(Le &L,int **&P,Graph &G,int &V);
int lastInsert(int *&p,int &x);
void myprint(Le &L,int**&p);
int main(){
   Le Length; // 某个顶点到其余所有顶点的最短距离
   int **Path;  // 路径
   int Vx;     //   某个顶点
   Graph G;    // 图
   init(Length,Path,G);
   printf("Enter the begin vertex:\n");
   scanf("%d",&Vx);
   Dijikstra(Length,Path,G,Vx);
   myprint(Length,Path);
}
void myprint(Le &L,int**&p){
    int i,j;
    for(i=0;i<6;i++){
        printf("%d:\t",L->le[i]);
        for(j=0;j<6;j++)
            printf("%d\t",p[i][j]);
        printf("\n");

    }
}
int lastInsert(int *&p,int &x){
     int i;
     for(i=0;i<VETNUM;i++){
        if(p[i]==-1){
          p[i] = x;
          return 1;
        }
     }
}
void init(Le &L,int **&P,Graph &G){
     int data[6][6] ={{-1,-1,10,-1,30,100},{-1,-1,5,-1,-1,-1},
                 {-1,2,-1,50,-1,-1},{-1,-1,-1,-1,-1,10},
                 {-1,-1,-1,20,-1,60},{-1,-1,-1,-1,-1,-1}};
     int data1[6][6] = {{-1,1,20,80,-1,400},{2,-1,-1,-1,-1,700},
                        {40,6,-1,4,-1,100},{-1,-1,-1,-1,4,-1},
                        {-1,-1,-1,-1,-1,3},{-1,-1,-1,-1,-1,-1}};
     int vextnum = 6;
     int i,j;
     G = (Graph)calloc(sizeof(g),1);
     G->p = (int**)malloc(sizeof(int*)*6);
     P = (int**)malloc(sizeof(int*)*6);
     L = (Le)calloc(sizeof(struct l),1);
     L->le = (int*)calloc(sizeof(int),6);
     L->isIn = (bool*)calloc(sizeof(bool),6);
     for(i=0;i<6;i++){
        G->p[i] = (int*)malloc(sizeof(int)*6);
        P[i] = (int *)calloc(sizeof(int),6);
     }
     G->vertNum = 6;
     for(i=0;i<vextnum;i++)
        for(j=0;j<vextnum;j++)
           G->p[i][j] = data[i][j],P[i][j]= -1;

    /***
     for(i=0;i<6;i++)
        printf("%d\n",L->isIn[i]);
     printf("xsaxas");
    */
}
void Dijikstra(Le &L,int **&P,Graph &G,int &V){
   int Vk;
   int i,j;
   int Min;
   int check=0;
   /**
      首先将L初始化  在这里面必有一条
      V 到其他顶点的最小值
   **/
   for(i=0;i<G->vertNum;i++){
       L->le[i] = G->p[V][i];
       //printf("%d\t",L->le[i]);
       if(L->le[i] > -1)
        check =1;
  }
  if(check==0)
    printf("Error!!"),exit(0);
   for(i=1;i<G->vertNum;i++){
        Min = INT_MAX;
      for(j=0;j<G->vertNum;j++)
       if(!L->isIn[j])
       {
           if(L->le[j]!=-1&&L->le[j]<Min)
           {
             Vk = j, Min= L->le[j];
           }
       }
      L->isIn[Vk] = true;          //  将距离Vx最近的点加入到另外一个集合中
                                   //  也就是说下一次不要比较

      lastInsert(P[V],Vk);
    for(j=0;j<G->vertNum;j++){

           if((G->p[Vk][j]!=-1)&&!L->isIn[j]
              &&(Min+G->p[Vk][j]<L->le[j]))
           {
                 L->le[j] = Min+G->p[Vk][j];
                 lastInsert(P[j],Vk);
                 lastInsert(P[j],j);
           }
           if(L->le[j]==-1&&(G->p[Vk][j]!=-1))
           {
                L->le[j] = Min+G->p[Vk][j];
                 lastInsert(P[j],Vk);
                 lastInsert(P[j],j);
           }

           }


     }


 }

Answer 2

Floyd，spfa，dijkstra用这三种算法任意一种都可求出每个点到V点的最短路，然后比较再输出最大的那个。

Answer 3

是我近视的超厉害还是你根本就没上传图，疑惑。

追问

图G是数据结构里的一个概念好不。。。题目的意思不是给一个图给你然后叫你解题。