100分求Dijkstra算法求解最小生成树问题 c或c++实现

最小生成树问题,一般都用prim 或者kruskal来实现. 但是Dijkstra算法较之kruskal算法,拥有更好的效率.我做了很长时间,没有结果.
数学算法是,在n-1个独立割集中,取每个割集的一条极小边,构成一个支撑树.此树,即为最小树.
过程为: R存放已取点,初始为R={1},S存放未取点,初始S={2,3....n}. 以邻接矩阵存取图.
先比较第一点a到其余各点边权值大小,选出权值最小点b.得到一条边.在S中去掉这一点.然后,比较a与b与此时S中各点权值,分别去掉各较小边权值,此时有n-1条,去最小边权值,或得第三点c,如此继续下去,一直到最后一点,即可获得最小生成树.
   这问题并不是简单特简单,我希望高手们能帮我实现下.多谢多谢

17 个解决方案

#1

boost::graph上有简单的实现。

#2

Kruscal算法   
  template   <class   NameType,   class   DistType>     
  void   Graph<   NameType,   DistType>::Kruskal   (   MinSpanTree   &T   )   { //克鲁斯卡尔算法   
        MSTEdgeNode   e;   
        MinHeap<   MstEdgeNode<int>   >   H   (CurrentEdges   ); //最小堆   
        int   NumVertices   =   VerticesList.last; //图中顶点个数   
        DisjointSets   F   (NumVertices); //连通分量   
        for   (   int   u=0;   u<NumVertices;   u++   ) //建立最小堆的数据   
    for   (   int   v=i+1;   v<NumVertices;   v++   )   
        if   (   Edge[u][v]   !=   MAXINT   )   { //插入新边值结点到最小堆中   
    e.tail   =   u;     e.head   =   v;     e.cost   =   w;     H.Insert   (e);   
        }   
        int   count   =   1; //生成树边计数   
        while   (   count   <   NumVertices   )   { //反复执行,   取n-1条边   
    e   =   H.RemoveMin   (   ); //从最小堆中退出具最小权值的边   
    u   =   F.Find   (   e.tail   );     v   =   F.Find   (   e.head   );//取两顶点所在集合的根   
    if   (   u   !=   v   )   { //不是同一集合,   说明不连通   
        F.Union   (   u,   v   );     T[count]   =   e;     count++; //合并,   连通它们,   该边加入生成树   
    }   
        }   
  }   

#3

给你抄个Prim算法吧   
  #define   MAX   10000   
  #define   N   100   //   最大顶点数   
    
  int   prim(w,n,v,tree)   
      int   w[][N];   //   邻接矩阵   
      int   n;   //   顶点数   
      int   v;   //   起始顶点   
      int   tree[][3];   //   存放边   
    
  {   int   i,j,k,p,min,c;   
      int   lowcost[N],closest[N];   
      for(i=0;i<n;i++){   
          closest[i]=v;   
          lowcost[i]=w[v][i];   
      }   
      c=0;p=0;   
      for(c=i=0;i<n-1;i++){   
          min=MAX;   
          for(j=0;j<n;j++)   
              if(lowcost[j]!=0&&lowcost[j]<min){   
                  min=lowcost[j];   
                  k=j;   
              }   
          tree[p][0]=closest[k];tree[p][1]=k;   
          tree[p][2]=min;p++;   
          c+=min;   
          lowcost[k]=0;   
          for(j=0;j<n;j++)   
              if(w[k][j]!=0&&w[k][j]<lowcost[j]){   
                  lowcost[j]=w[k][j];   
                  closest[j]=k;   
              }   
      }   
      return   c;   //   返回最小代价   
  }

#4

Prim算法与Kruskal算法都是求含权无向图的最小耗费生成树，但方法截然不同。并且Prim算法与Dijkstra算法十分类似。

#5

Jarnik.Prim算法
在这个方法中，开始时所有的边都是排序的，但是准备加入生成树的边不仅不会在树中产生环路，而且也和树中已经有的一个顶点关联。
JarnikPrimAlgorithm(带权连通无向图 graph)
tree = null;
edges = 按权值大小排序的graph的全部边
for i = 1 到|V| - 1
for j = 1 到 |edges|
if edges 中的边edges[j]和tree中的边不会产生回路并且和tree中的一个顶点关联
将edges[j]添加进tree;
break;

Dijkstra算法
JarnikPrimAlgorithm(带权连通无向图 graph)
tree = null;
edges = 未排序的graph全部边;
for j = 1 到 |edges|
将edges[j]添加进tree;
if 在tree中有环路
从这个环路中删除权值最大的一条边;

#6

http://student.zjzk.cn/course_ware/data_structure/web/tu/tu7.5.2.htm

#7

dijkstra算法的C语言实现



    这两天有一个实现最佳路径的路由算法的任务，选用著名的dijkstra算法——单源最短带权路径的算法。算法原理主要就是已知源节点（v）和n个节点间代价函数（有向网络矩阵cost），通过不断将节点加入到一个节点子集S中，使得经过加入S后的各节点的路径代价是最小的，直至S节点包含了所有的n个节点停止。（具体算法阐明网上很多资料）。闲话少说，直接附程序吧～

/*
readme:
first,you need to input the node number, the cost matrix and the source node;
then the program will compute the best path.
finally,the program will output the lowest distance to the destination node, the pre-node and show the best path.
*/


＃i nclude<stdio.h>
＃i nclude <stdlib.h>
//Dijkstra算法实现函数
void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
  int i;
  int j;
    int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值
    int *s ;//定义具有最短路径的节点子集s
  s = (int *)malloc(sizeof(int) * n);
    //初始化最小路径代价和前一跳节点值
    for (i = 1; i <= n; i++)
    {
        dist[i] = cost[v][i];
        s[i] = 0;
        if (dist[i] == maxint)
        {
            prev[i] = 0;
        }
        else
        {
            prev[i] = v;
        }
    }
    dist[v] = 0;
    s[v] = 1;//源节点作为最初的s子集


    for (i = 1; i < n; i++)
    {
        int temp = maxint;
        int u = v;
        //加入具有最小代价的邻居节点到s子集
        for (j = 1; j <= n; j++)
        {
            if ((!s[j]) && (dist[j] < temp))
            {
                u = j;
                temp = dist[j];
            }
        }
        s[u] = 1;
        //计算加入新的节点后，更新路径使得其产生代价最短
        for (j = 1; j <= n; j++)
        {
            if ((!s[j]) && (cost[u][j] < maxint))
            {
                int newdist = dist[u] + cost[u][j];
                if (newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
        }
    }
}
//展示最佳路径函数
void ShowPath(int n,int v,int u,int *dist,int *prev)
{


 int j = 0;
 int w = u;
 int count = 0;
 int *way ;
 way=(int *)malloc(sizeof(int)*(n+1));
 //回溯路径
 while (w != v)
 {
  count++;
  way[count] = prev[w];
  w = prev[w];
 }
 //输出路径
 printf("the best path is:\n");
 for (j = count; j >= 1; j--)
 {
  printf("%d -> ",way[j]);
 }
 printf("%d\n",u);


}
//主函数，主要做输入输出工作
void main()
{
 int i,j,t;
  int n,v,u;
  
 int **cost;//代价矩阵
 int *dist;//最短路径代价
 int *prev;//前一跳节点空间


 printf("please input the node number: ");
  scanf("%d",&n);
  printf("please input the cost status:\n");
    
 cost=(int **)malloc(sizeof(int)*(n+1));


  for (i = 1; i <= n; i++)
  {
      cost[i]=(int *)malloc(sizeof(int)*(n+1));
  }
  //输入代价矩阵
  for (j = 1; j <= n; j++)
  {
      for (t = 1; t <= n; t++)
      {
          scanf("%d",&cost[j][t]);
      }
  }
    
  dist = (int *)malloc(sizeof(int)*n);
  prev = (int *)malloc(sizeof(int)*n);


  printf("please input the source node: ");
  scanf("%d",&v);
  //调用dijkstra算法  
  Dijkstra(n, v, dist, prev, cost);
  printf("*****************************\n");
 printf("have confirm the best path\n");
 printf("*****************************\n");
 for(i = 1; i <= n ; i++)
 {
  if(i!=v)
  {
   printf("the distance cost  from node %d to node %d is %d\n",v,i,dist[i]);
   printf("the pre-node of node %d is node %d \n",i,prev[i]);
   ShowPath(n,v,i, dist, prev);
  }
 }
}
//////////////////

http://www.blog.edu.cn/user4/259446/archives/2007/1981688.shtml

#8

这个照着书作就可以了。

#9

输入时，将s,t,x,y,z五个点按照1,2,3,4,5起别名，输入格式按照下图例所示
当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起始点
比如计算结果v1v4v2表示从点1到点2经过1，4，2为最短路径
Dijkstra算法的完整实现版本，算法的源代码
/* Dijkstra.c
 
    Copyright (c) 2002, 2006 by ctu_85
    All Rights Reserved.
*/
#include "stdio.h"
#include "malloc.h"
#define maxium 32767
#define maxver 9 /*defines the max number of vertexs which the programm can handle*/
#define OK 1
struct Point
{
       char vertex[3];
       struct Link *work;
       struct Point *next;
};
struct Link
{
       char vertex[3];
       int value;
       struct Link *next;
};
struct Table /*the workbannch of the algorithm*/
{
       int cost;
       int Known;
       char vertex[3];
       char path[3];
       struct Table *next;
};
int Dijkstra(struct Point *,struct Table *);
int PrintTable(int,struct Table *);
int PrintPath(int,struct Table *,struct Table *);
struct Table * CreateTable(int,int);
struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the smallest value reside in the table*/
int main()
{
       int i,j,num,temp,val;
       char c;
       struct Point *poinpre,*poinhead,*poin;
       struct Link *linpre,*linhead,*lin;
       struct Table *tabhead;
       poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point));
       poin->next=NULL;
       poin->work=NULL;
       restart:
       printf("Notice:if you wanna to input a vertex,you must use the format of number!\n");
       printf("Please input the number of points:\n");
       scanf("%d",&num);
       if(num>maxver||num<1||num%1!=0)
       {
              printf("\nNumber of points exception!");
              goto restart;
       }
       for(i=0;i<num;i++)
       {
              printf("Please input the points next to point %d,end with 0:\n",i+1);
              poin=(struct Point *)malloc(sizeof(struct Point));
              poinpre->next=poin;
              poin->vertex[0]='v';
              poin->vertex[1]='0'+i+1;
              poin->vertex[2]='\0';
              linpre=lin=poin->work;
              linpre->next=NULL;
              for(j=0;j<num-1;j++)
              {
              printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1);
              scanf("%d",&temp);
              if(temp==0)
                     {
                     lin->next=NULL;
                     break;
                     }
              else
                     {
                     lin=(struct Link *)malloc(sizeof(struct Link));
                     linpre->next=lin;
                     lin->vertex[0]='v';
                     lin->vertex[1]='0'+temp;
                     lin->vertex[2]='\0';
                     printf("Please input the value betwixt %d th point towards %d th point:",i+1,temp);
                     scanf("%d",&val);
                     lin->value=val;
                     linpre=linpre->next;
                     lin->next=NULL;
                     }
              }
              poinpre=poinpre->next;
              poin->next=NULL;
       }
       printf("Please enter the vertex where Dijkstra algorithm starts:\n");
       scanf("%d",&temp);
       tabhead=CreateTable(temp,num);
       Dijkstra(poinhead,tabhead);
       PrintTable(temp,tabhead);
       return OK;
}
struct Table * CreateTable(int vertex,int total)
{
       struct Table *head,*pre,*p;
       int i;
       head=pre=p=(struct Table *)malloc(sizeof(struct Table));
       p->next=NULL;
       for(i=0;i<total;i++)
       {
              p=(struct Table *)malloc(sizeof(struct Table));
              pre->next=p;
              if(i+1==vertex)
              {
                     p->vertex[0]='v';
                     p->vertex[1]='0'+i+1;
                     p->vertex[2]='\0';
                     p->cost=0;
                     p->Known=0;
              }
              else
              {
                     p->vertex[0]='v';
                     p->vertex[1]='0'+i+1;
                     p->vertex[2]='\0';
                     p->cost=maxium;
                     p->Known=0;
              }
              p->next=NULL;
              pre=pre->next;
       }
       return head;
}
int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/
{
       int costs;
       char temp;
       struct Point *poinhead=p1,*now;
       struct Link *linna;
       struct Table *tabhead=p2,*searc,*result;
       while(1)
       {
              now=FindSmallest(tabhead,poinhead);
              if(now==NULL)
                     break;
              result=p2;
              result=result->next;
              while(result!=NULL)
              {
                     if(result->vertex[1]==now->vertex[1])
                            break;
                     else
                            result=result->next;
              }
              linna=now->work->next;
              while(linna!=NULL) /* update all the vertexs linked to the signed vertex*/
              {
                     temp=linna->vertex[1];
                     searc=tabhead->next;
                     while(searc!=NULL)
                     {
                            if(searc->vertex[1]==temp)/*find the vertex linked to the signed vertex in the table and update*/
                            {
                                   if((result->cost+linna->value)<searc->cost)
                                   {
                                   searc->cost=result->cost+linna->value;/*set the new value*/
                                   searc->path[0]='v';
                                   searc->path[1]=now->vertex[1];
                                   searc->path[2]='\0';
                                   }
                                   break;
                            }
                            else
                                   searc=searc->next;
                     }
                     linna=linna->next;
              }
       }
       return 1;
}
struct Point * FindSmallest(struct Table *head,struct Point *poinhead)
{
       struct Point *result;
       struct Table *temp;
       int min=maxium,status=0;
       head=head->next;
       poinhead=poinhead->next;
       while(head!=NULL)
       {
              if(!head->Known&&head->cost<min)
              {
                     min=head->cost;
                     result=poinhead;
                     temp=head;
                     status=1;
              }
              head=head->next;
              poinhead=poinhead->next;
       }
       if(status)
       {
              temp->Known=1;
              return result;
       }
       else
              return NULL;
}
int PrintTable(int start,struct Table *head)
{
       struct Table *begin=head;
       head=head->next;
       while(head!=NULL)
       {
              if((head->vertex[1]-'0')!=start)
                     PrintPath(start,head,begin);
              head=head->next;
       }
       return OK;
}
int PrintPath(int start,struct Table *head,struct Table *begin)
{
       struct Table *temp=begin->next,*p,*t;
       p=head;
       t=begin;
       if((p->vertex[1]-'0')!=start&&p!=NULL)
       {
              while(temp->vertex[1]!=p->path[1]&&temp!=NULL)
                     temp=temp->next;
              PrintPath(start,temp,t);
              printf("%s",p->vertex);
       }
       else
              if(p!=NULL)
              printf("\n%s",p->vertex);
       return OK;
}

#10

Prim算法代码分析
http://blog.csdn.net/ctu_85/archive/2006/12/16/1445156.aspx
Kruskal算法代码分析
http://blog.csdn.net/ctu_85/archive/2006/12/16/1445147.aspx

#11

9楼的可不可以搞个中文啊··
哎。。

#12

  yshuise的专栏
  图算法《c++算法》（二）
新一篇: KMP算法（《算法导论》）
//d路堆
#ifndef PQI_INCLUDE_H
#define PQI_INCLUDE_H
#include <vector>
using std::vector;
template <class keyType>
class PQi
...{
private:
    int d;
    int N;
    vector<int>p, q;
    const vector<keyType>&a;
public:
    PQi(int N, const vector<keyType>&a, int d = 3):a(a),p(N+1, 0),
        q(N+1, 0),N(0),d(d)...{   }
    int  empty()const;
    void exch(int i, int j);
    void fixUp(int k);
    void fixDown(int k, int N);
    void insert(int v);
    int  getmin();
    void lower(int k);
};
#endif#ifndef INSTANCE_PQI_INCLUDE
#define INSTANCE_PQI_INCLUDE
#include "PQi.h"
template<class keyType>
void PQi<keyType>::exch(int i, int j)
...{
    int t = p[i];
    p[i] = p[j];
    p[j] = t;
    q[p[i]] = i;
    q[p[j]] = j;
}
template<class keyType>
void PQi<keyType>::fixUp(int k)
...{
    while (k > 1 && a[p[(k+d-2)/d]] > a[p[k]])
    ...{
      exch(k, (k+d-2)/d);
      k = (k+d-2)/d;
    }
}
template<class keyType>
void  PQi<keyType>::fixDown(int k, int N)
...{
    int j;
    while((j = d*(k-1) + 2) <= N)
    ...{
        for(int i = j+1; i < j+d && j <= N; i++)
        if(a[p[j]] > a[p[i]]) j = i;
        if(!(a[p[k]] > a[p[j]])) break;
        exch(k, j);
        k = j;
    }
}
template<class keyType>
void PQi<keyType>::insert(int v)
...{
        p[++N] = v;
        q[v] = N;
        fixUp(N);
}
template<class keyType>
int PQi<keyType>::getmin()
...{
        exch(1, N);
        fixDown(1, N-1);
        return p[N--];
}
template<class keyType>
int PQi<keyType>::empty()const 
...{ 
    return N == 0;
}
template<class keyType>
void PQi<keyType>::lower(int k)
...{
    fixUp(q[k]); 
}

#endif// Densegraph__.cpp : Defines the entry point for the console application.
//SPT(单源最短路径)：给定一个起始顶点s，找到s到图中的其他各顶点的最短路径。
//全源最短路径：找出连接图中各对顶点的最短路径。
//MST：最小生成树，权值最小的树。
//关于权值：权值最好是0——1之间，这样更具有通用性，即使权值不为零，也可以同时缩小多少倍，
// 比如1/10, 1/100, 1/1000,1/10000等，视最大值的情况而定。
#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include "PQi.h"
#include "PQi_INS.H"
using namespace std;

class DenseGraph
...{
private:
    struct Edge
    ...{   
        Edge(int vv, int ww , double wt):v(vv),w(ww),weight(wt)...{ }
        int  v;
        int  w;
        double  weight;
    };
    int Vcnt;
    int Ecnt;
    bool digraph;//判断是不是有向图
    vector<vector<Edge*> >adj;
    int i;
    int v;
    vector<double> wt;
    vector<Edge*>fr, mst;
    vector<Edge* > spt;
    vector<vector<Edge*> >p;
    vector<vector<double> >d;
    Edge* ftr[15];
    int count;

public:
    DenseGraph(int V, bool digraph_ = false)
    ...{  
        Edge(0, 0, 0);
        Vcnt = V;
        Ecnt = 0;
        digraph = digraph_;
        adj.resize(V, vector<Edge*>(V,0) );
        i = 0;
        v = V;
        wt.resize(V, V);
        fr.resize(V, 0);
        mst.resize(V, 0);
        spt.resize(V, 0);
        p.resize(V, vector<Edge* >(V,0) );
        d.resize(V, vector<double>(V,V) );
        for(int f = 0; f < 15; f++)
            ftr[f] = 0;
        count = -1;
        
    }
 int V() const ...{ return Vcnt; }
 int E() const ...{ return Ecnt; }
 bool directed() const ...{ return digraph; }
 void insert(Edge* e)
 ...{   
    
    int v = e->v;
    int w = e->w;
    if(0 == adj[v][w])
    ...{
        Ecnt++;
        adj[v][w] = e;
    }
    if(!digraph)
    ...{
        adj[w][v] = e;
    }
 }
 void remove(int v, int w)
 ...{
    
   if(0 != adj[v][w])
   ...{
       Ecnt--;
       adj[v][w] = 0;
   }
   if(!digraph)
   ...{
     adj[w][v] = 0;
   }
 }

Edge* edge(int v, int w)  
...{  
     if(0 != adj[v][w])
     ...{
         return adj[v][w];
     }
     else
     ...{
          return 0;
     }
    
}

Edge* Begin()...{ i = -1; return Next(); }
Edge* Next()
...{
    for(i++; i < V(); i++)
    ...{
    
        if(edge(v, i))
        return adj[v][i];
    }

}
bool End() const ...{ return i >= V(); }

//不能用于负边，而且是用于有向树,求s到每个点的最短路径。
//Dijkstra算法：一次增加一条边以扩展SPT，每一次要更新对于与该边结束顶点相邻接的所有顶点
//到达树的距离，与此同时还要检查所有非树顶点以找出一条边从而将其移到树种，此边的目的顶点是一个
//非树顶点，而且与源点有最小的距离。
//wt中保存着从源点到其他顶点的已知最短路径
//spt记录从源点到索引顶点的最短路径的最后一条边。
//边松弛：检查沿着一条给定的边是否可以给出到达其目的顶点的一条新的路径
//if(wt[w] > wt[v] + e ->weight){ wt[w] = wt[v] + e->weight; spt[w] = e; }

void SPT_Dijkstra(int s)
...{
    PQi<double>PQ(V(), wt);
    for(v = 0; v < V()-1; v++)
    PQ.insert(v);
    wt[s] = 0;
    PQ.lower(s);
    while(!PQ.empty())
    ...{
        int v = PQ.getmin();
        if(v != s && 0 == spt[v]) return;
        for(Edge* e = Begin(); !End(); e = Next())
        ...{
            int w = e->w;
            double P = wt[v] + e->weight;
            if(P < wt[w])
            ...{
                wt[w] = P;
                PQ.lower(w);
                spt[w] = e;
            }
        }
    }
}

Edge* pathR(int v) const ...{ return spt[v]; }
double dist(int v) const ...{ return wt[v]; }

 ~DenseGraph()
 ...{ 
     for(int i = 0; i < V(); i++)
       delete ftr[i];
 }


};


int main(int argc, char* argv[])
...{   
    //DenseGraph oop(15);
    /**//*(oop.insert(oop.adapter_insert(0, 2, 0.29));
    oop.insert(oop.adapter_insert(0, 6, 0.34));
    oop.insert(oop.adapter_insert(0, 7, 0.31));
    oop.insert(oop.adapter_insert(0, 1, 0.32));
    oop.insert(oop.adapter_insert(0, 5, 0.53));
    oop.insert(oop.adapter_insert(1, 7, 0.21));
    oop.insert(oop.adapter_insert(7, 6, 0.25));
    oop.insert(oop.adapter_insert(7, 4, 0.46));
    oop.insert(oop.adapter_insert(6, 4, 0.50));
    oop.insert(oop.adapter_insert(3, 4, 0.34));
    oop.insert(oop.adapter_insert(3, 5, 0.18));
    oop.insert(oop.adapter_insert(5, 4, 0.40));
    DenseGraph oop(15, true);//有向树
    oop.insert(oop.adapter_insert(0, 2, 0.29));
    oop.insert(oop.adapter_insert(0, 6, 0.34));
    oop.insert(oop.adapter_insert(0, 7, 0.31));
    oop.insert(oop.adapter_insert(0, 1, 0.32));
    oop.insert(oop.adapter_insert(0, 5, 0.53));
    oop.insert(oop.adapter_insert(1, 7, 0.21));
    oop.insert(oop.adapter_insert(7, 6, 0.25));
    oop.insert(oop.adapter_insert(7, 4, 0.46));
    oop.insert(oop.adapter_insert(6, 4, 0.50));
    oop.insert(oop.adapter_insert(3, 4, 0.34));
    oop.insert(oop.adapter_insert(3, 5, 0.18));
    oop.insert(oop.adapter_insert(5, 4, 0.40));
    oop.SPT_Dijkstra(5);
     return 0;
}

 
 

#13

各位大哥 我题目说得是:最小生成树问题  不是最短路径问题

#14

我觉着dij是求单源最短路的，不是求MST的……

#15

up

#16

我也想知道，正在找這方面的資料~~~~~

#17

#include<stdio.h>
#include<limits.h>
#include<process.h>
#include<string.h>
#define OK 1
#define INFINITY 10000 // 用整型最大值代替∞
#define MAX_VERTEX_NUM 10 // 最大顶点个数
typedef char VertexType[3]; 
typedef int status;
typedef struct Graph{
  VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量（一维数组）
  int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
  int vexnum,arcnum; // 图的当前顶点数和弧数
}Graph;

int Locate(Graph G,VertexType c)
{
int i;
for(i=0;i<G.vexnum;i++)
if(strcmp(c,G.vexs[i])==0)
return i;
   return -1;

}
status Create(Graph &G)
{
int i,j,k,w;
char v[3],u[3];
printf("请输入顶点数，边数：");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("\n请输入顶点向量:");
for(i=0;i<G.vexnum;i++)
{
scanf("%s",&G.vexs[i]);
}
    for(i=0;i<G.vexnum;i++)
      for(j=0;j<=G.vexnum;j++)
  G.arcs[i][j]=INFINITY;
printf("\n请输入边所依附的两顶点及权值:\n");
for(k=0;k<G.arcnum;k++)
{
scanf("%s%s%d",&v,&u,&w);
i=Locate(G,v);
        j=Locate(G,u);
G.arcs[i][j]=w;
}
return OK;
}

void ShorttestPath(Graph G,int v0,int D[],int P[][MAX_VERTEX_NUM])
{
   int v,w,i,j,min;
   int final[MAX_VERTEX_NUM];
   for(v=0;v<G.vexnum;v++)
{ //初始化
      final[v]=0; D[v]=G.arcs[v0][v];
      for(w=0;w<G.vexnum;++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.vexnum;i++) { //求其余顶点的最短路径
  min=INFINITY;
  for(w=0;w<G.vexnum;++w)
  {
    if(!final[w]) //顶点w不在集合S中
      if(D[w]<min) 
  {
 v=w;
 min=D[w];
  }//顶点w离顶点v0更近
  }
  final[v]=1; //离顶点v0最近的v加入集合S
  for(w=0;w<G.vexnum;++w) //更新当前最短路径及距离
  if (!final[w]&&((min+G.arcs[v][w])<D[w]))
  {
        D[w]=min+G.arcs[v][w];
        for(j=0;j<G.vexnum;++j)
           P[w][j]=P[v][j];
           P[w][w]=1; 
  }
  }
   
}

void main()
{
   Graph G;
   int i,j,k=0;
   int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
   int D[MAX_VERTEX_NUM];
   Create(G);
   printf("%d个顶点%d条弧的有向图为：",G.vexnum,G.arcnum);
   for(i=0;i<G.vexnum;i++)
   printf("%3s",G.vexs[i]);
   ShorttestPath(G,k,D,P);
  printf("\nG.arcs:\n");
   for(i=0;i<G.vexnum;i++)
   {
   for(j=0;j<G.vexnum;j++)
  printf("%8d",G.arcs[i][j]);
    printf("\n");
   }
   printf("最短路径数组P[i][j]如下:\n");
   for(i=0;i<G.vexnum;i++)
   {
   for(j=0;j<G.vexnum;j++)
         printf("%6d",P[i][j]);
       printf("\n");
   }
   printf("v0到各顶点最短路径长度为:\n");

   for(i=1;i<G.vexnum;i++)
   printf("v0-%s:%d\n",G.vexs[i],D[i]);
}