void binSort(SortObject * pvecter)/*按递增序进行二分法插入排序*/
       {
          int i ,j ,left,mid ,right; 
           RecordNode temp;
          for(i=1;i<pvector->n;i++)
           {
            temp=pvector->record[i];
            left=0;right=i-1;/*置已排序区间的下，上界初值*/
              while(left<=right)
               {
                mid=(left+right)/2;/*mid指向已排序区间的中间位置*/
                if(temp.key<pvector->rocord[mid].key)
                     right=mid-1;/*插入元素应在左子区间*/
                else
              left=mid+1;/*插入元素应在右子区间*/
                }
          for(j=i-1;j>=left;j--)
               pvector->record[j+1]=pvector->recod[j];/*将排序码大于Ki的记录后移*/
               if(left!=i)pvector->record[left]=temp;
            }
         }
   
 void dijkstra(GraphMatrix graph, Path dist[])/*Dijkstra算法*/ 
   {
      int i,j,minvex;
        AdjType min;
      init(&graph,dist);    /* 初始化，此时集合U中只有顶点v0*/
     for(i = 1; i < graph.n; i++) 
       {
          min=MAX;    
          minvex=0;
         for (j = 1; j < graph.n; j++)  /*在V-U中选出距离值最小顶点*/
            if( graph.arcs[j][j] == 0 && dist[j].length < min )
            {
                min=dist[j].length; 
                minvex=j;  
             }
            if(minvex == 0)
             break;               /* 从v0没有路径可以通往集合V-U中的顶点 */
          graph.arcs[minvex][minvex] = 1;  /* 集合V-U中路径最小的顶点为minvex */
            for (j = 1; j < graph.n; j++)    /* 调整集合V-U中的顶点的最短路径 */
               {    
                  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  binSort()
                }
             }
           }
   int main()
  {
   int v0=0,i,j,k,w;
    clrscr();
  G=(MGraph *)malloc(sizeof(MGraph));
  printf("Input totals of Vertexs and Edges(e.g:Vertex_Totals,Edge_Totals):\n");/*对图的初始化，给图的顶点数和边数赋值*/
    scanf("%d,%d",&G->n,&G->e);
   printf("Input information for Vertexs(e.g:Vertex_SN<CR>):\n");/*给图的每个顶点输入一个序列号*/
   for(i=0;i<G->n;i++)
     scanf("%s",G->vexs[i]);
  for(i=0;i<G->n;i++)
   for(j=0;j<G->n;j++)
    G->edges[i][j]=INFINITY;/*设定一个最大值给每条边，让每个顶点初始化的时候相当于权值无穷大即互不相连*/
  printf("Input every edge together two Vertexs' SN(e.g:i,j):\n");
  for(k=0;k<G->e;k++)? ? /*输入要进行赋值的边所确定的两个顶点*/
  {
   scanf("%d,%d",&i,&j);
    printf("weight of the edge<v%d,v%d>:",i,j);/*给固定的边赋值*/
     scanf("%d",&G->edges[i][j]);
    }
  void creatgraph(AdGraph G)
  int exist_path_BFS(Adlist G,int i,int j)
  void  quickSort(SortObject  * pvector , int l,int r)
   void dijkstra(GraphMatrix graph, Path dist[])/*
      for (i = 0; i < graph.n; i++)
          printf("(%.0f %d)", dist[i].length,dist[i].prevex);
         return  0
  }
请高手帮帮忙看看我哪里错了,急!!谢谢!

 
 

先问一下,对路径数组排序如何能改进Dijkstra算法?
题目要求用快速排序,你怎么用了很*个性*的二分插入排序?

代码疑问:
if(graph.arcs[j][j] == 1)  continue;怎么两个j?
dijkstra()函数里怎么能这样调用函数,还不带分号: void  binSort()
main里面有好多同样错误.

一定要回答第一个问题呀~

谢谢这位高手。
我是在一篇论文上看到这个方法的。现摘抄一小段：
   
    高效的搜索最小权值的顶点的方法是最优化最短路径算法的关键。对顶点的权值排序后，再搜索最小权值，能极大地减少扫描时间，首先，使用快速排序函数对最短路径值数组进行排序，并且使位置指针指向当前最小权值在地址数组的位置。
  接下来，使用邻接表实现松弛操作。即dijkstra算法中未标记节点的权值的步骤：  if dist[j]+cost[j,k]<dist[k]
     then dist[k]=dist[j]+cost[j,k]
   此时需要使用地址数组重新排序。

恩，因为急急忙忙，我可能写错了很多东西。现在我想问高手一下，在图以邻接表存储时，如何实现快速排序？还有我们在《算法与数据结构》中学的dijkstra算法是基与邻接矩阵的吧，现在换成是邻接表了，它的算法又是怎样的呢？
    急，还是希望高手多多指点哈。

  还有就是高手对这个提出疑问：if(graph.arcs[j][j] == 1)  continue
  我刚翻了翻书，我的那本《数据结构》中确实就是这样写的，不知书是否出错了。
    现在我都不想使用那个二分法插入排序了，因为不会用，呵呵。

我还是不认为排序有用...#_#

怎么会没有用呢?排好序之后,搜索最短权值就快得多啊!
现在我所迷惑的是当存储结构为邻接表之后,那个dijkstra算法是怎么样的呢?我不知道了,请高手帮帮我好吗?

顶先