#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
//#include <vector>
#define MAX_VERTEX_NUM 20
#define INFINITY 10000
#define maxWeight 10000
typedef int PathMatrix[MAX_VERTEX_NUM];
typedef int ShortestPathTable[MAX_VERTEX_NUM];

typedef char Vertex_Type[5];
typedef enum
{
    DG,UDG
}Graph_Kind;
typedef struct Arc_Node
{
    int adjvex;    //邻接点在向量表中的位置
    struct Arc_Node *nextarc;
    int weight;    //权
    int *info;
}Arc_Node;
typedef struct Vertex_Node
{
    Vertex_Type data;
    Arc_Node *firstarc;
}Vertex_Node;
typedef struct
{
    Vertex_Node vexs[MAX_VERTEX_NUM];//顶点向量
    int vexnum;        //顶点数
    int arcnum;
    Graph_Kind kind;
}ALGraph;
//初始化图中的有关信息
void Init_ALGraph(ALGraph &G)
{   
    int w;
    //printf("输入图的类型(DG:1 UDG:2):");
    cout<<"输入图的类型(DG:1 UDG:2):";
    cin>>w;
    //scanf("%S",&G.kind);
    cout<<"输入图的顶点数:";
    cin>>G.vexnum;
    cout<<"输入图的边数:";
    cin>>G.arcnum;
    int i;
    cout<<"输入定点值:";
    for(i=0;i<G.vexnum;++i)
    {
        cin>>G.vexs[i].data;
        G.vexs[i].firstarc=NULL;
    }
}
//获取定点在向量中的位置 如果出错就终止运行
int Get_Vertex_Location(ALGraph G,Vertex_Type v)
{
    int i;
    for(i=0;i<G.vexnum;++i)
        if(strcmp(v,G.vexs[i].data)==0)
            return i;
    exit(0);
}
/*int Get_Vertex_Location(ALGraph G,Vertex_Type v)
{
    for(int i=0;i<G.vexnum;++i)
    {
        if(G.vexs[i].data==v)
            return i;
        else
        return 0;
    }
}*/
void Greate_ALGraph(ALGraph &G)
{
    Init_ALGraph(G);

    Vertex_Type v1,v2;
    int i,m,n;
    cout<<"输入图形的边:";
    for(i=0;i<G.arcnum;++i)            //输入并构造邻接表
    {
        cin>>v1>>v2;   
        m=Get_Vertex_Location(G,v1);    //确定i和j在G中位置，即顶点的序号
        n=Get_Vertex_Location(G,v2);

        Arc_Node *p1,*p2;
        p1=(Arc_Node*)malloc(sizeof(Arc_Node));
        p1->adjvex=n;    //对弧结点赋邻接点位置信息
        p1->nextarc=G.vexs[i].firstarc;
        G.vexs[i].firstarc=p1;
        switch(G.kind)
        {
        case DG:
            break;
   
        case UDG:
            p2=(Arc_Node*)malloc(sizeof(Arc_Node));
            p2->adjvex=m;
            p2->nextarc=G.vexs[n].firstarc;
            G.vexs[n].firstarc=p2;    //头插入
            break;
        }

    }
}
void ShortestPath_DIJ(ALGraph &G,int v0,PathMatrix &P,ShortestPathTable &D)
{
    int v,w,i,min;
    int final[MAX_VERTEX_NUM];
    Arc_Node *p;
    for(v=0;v<G.vexnum;v++) {
        final[v]=false;
        D[v]=INFINITY;
    }
    for(p=G.vexs[v0].firstarc;p;p=p->nextarc) {
        D[p->adjvex]=*(int *)(p->info);
        if(P[i]<maxWeight&&P[i]!=0)
        {    P[p->adjvex]=v0;
            P[p->adjvex]=p->adjvex;
        }
        else
            P[i]=-1;
    }
   
    D[v0]=0;
    final[v0]=true;
   
    for(i=1;i<G.vexnum;i++) {
        min=INFINITY;
        for(w=0;w<G.vexnum;w++)
            if(!final[w]&&D[w]<min) {
                v=w;
                min=D[w];
            }
            final[v]=true;
            for(p=G.vexs[v].firstarc;p;p=p->nextarc) {
                w=p->adjvex;
                if(!final[w] && min<INFINITY && min+*(int *)(p->info)<D[w]) {
                    D[w]=min+*(int *)(p->info);
                    P[w]=P[v];
                    P[p->adjvex]=w;
                    

                }
            }
    }
}
   
void Print_ALGraph(ALGraph G)
{
    int i;
    for(i=0;i<G.vexnum;++i)
    {
        Arc_Node *p=G.vexs[i].firstarc;
        while(p)
        {
            switch(G.kind)
            {
            case UDG:
                cout<<G.vexs[i].data<<"--";
                cout<<G.vexs[p->adjvex].data;
                break;
            case DG:
                cout<<G.vexs[i].data<<"--";
                cout<<G.vexs[p->adjvex].data<<endl;
                break;
            }
        p=p->nextarc;
        }
    }
}
int main()
{
    ALGraph G;
    int v;
    int n;
    PathMatrix *P=new PathMatrix[n] ;
    ShortestPathTable *D=new ShortestPathTable[n];
    Greate_ALGraph( G );
    ShortestPath_DIJ(G,v,P,D);
    Print_ALGraph( G );
    return 0;
}

[ 本帖最后由 世界模型 于 2010-12-7 22:11 编辑 ]

多了个int getweight(int v1,int v2)，忘了删了

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20//预定义最大顶点个数
#define MAX_VALUE 1000//代表无穷

/*定义辅助表 用于记录最短路径*/
struct
{
    int style;//标记是否在最短路径中 如果在职位1 否则为0
    int length;//记录最短的路径大小
}D_table[MAX_VERTEX_NUM] = {0};

/*图的存储结构采用邻接表*/
typedef char Vertex_Type[5];//顶点的类型

/*定义图的类型为枚举类型*/
typedef enum
{
    DG,UDG
}Graph_Kind;
/*定义弧和弧头信息结构体*/
typedef struct Arc_Node
{
    int adjvex;    //邻接点在向量表中的位置
    int weight;    //权
    struct Arc_Node *nextarc;//指向下一个弧
}Arc_Node;

/*定义顶点向量表结点*/
typedef struct Vertex_Node
{
    Vertex_Type data;
    Arc_Node *firstarc;
}Vertex_Node;

typedef struct
{
    Vertex_Node vexs[MAX_VERTEX_NUM];//顶点向量
    int vexnum;        //顶点数 零下标不使用
    int arcnum;    //弧的条数
    Graph_Kind kind;//图的类型
}ALGraph;

/*初始化图*/
void Init_Graph(ALGraph &G)
{   
    int w;
label:
    printf("输入图的类型(DG:1 UDG:2):");
    scanf("%d", &w);
    if( 1 == w )
        G.kind = DG;
    else if( 2 == w )
        G.kind = UDG;
    else
    {
        printf("输入信息有误!\n");
        goto label;
    }
    printf("输入图的顶点数:");
    scanf("%d", &G.vexnum);
    printf("输入图的边数:");
    scanf("%d", &G.arcnum);
    printf("输入顶点值(例如:v1, v2...):");
    for( w=1; w<=G.vexnum; ++w)
    {
        scanf("%s", G.vexs[w].data);
        G.vexs[w].firstarc=NULL;
    }
}
/*获取定点在向量中的位置 如果出错就终止运行*/
int Get_Vertex_Location(ALGraph G,Vertex_Type v)
{
    int i;
    strcpy(G.vexs[0].data, v);
    for( i=G.vexnum; strcmp(v, G.vexs[i].data) !=0; --i );

    return i;
}
/*连接顶点之间的弧*/
void Create_Graph(ALGraph &G)
{
    Init_Graph(G);

    Vertex_Type v1,v2;
    int i, v1_s, v2_s, w;

    printf("\t输入图形的边 vx whitespace vy\n");
    for(i=1; i<=G.arcnum; ++i)            //输入并构造邻接表
    {
label:   
        scanf("%s%s", v1, v2);
        scanf("%d",&w);   
        v1_s = Get_Vertex_Location(G,v1);    //确定i和j在G中位置，即顶点的序号
        v2_s = Get_Vertex_Location(G,v2);
        if( !v1_s || !v2_s )
        {
            printf("\t输入错误!");
            goto label;
        }

        Arc_Node *p1;
        p1 = (Arc_Node*) malloc (sizeof(Arc_Node));
        p1->adjvex=v2_s;    //对弧结点赋邻接点位置信息
        p1->weight = w;
        p1->nextarc = G.vexs[v1_s].firstarc;//头插入
        G.vexs[v1_s].firstarc = p1;

        if( UDG == G.kind )
        {
            Arc_Node *p2;
            p2 = (Arc_Node*) malloc (sizeof(Arc_Node));
            p2->adjvex = v1_s;
            p2->weight = w;
            p2->nextarc = G.vexs[v2_s].firstarc;
            G.vexs[v2_s].firstarc = p2;    //头插入
        }
    }
}
/* 打印图 */
void Print_Graph(ALGraph G)
{
    int i;
    for(i=1;i<=G.vexnum;++i)
    {
        Arc_Node *p=G.vexs[i].firstarc;
        while(p)
        {
            switch(G.kind)
            {
            case UDG:
                printf("%s -- %s %d\n", G.vexs[i].data, G.vexs[p->adjvex].data, p->weight);
                break;
            case DG:
                printf("%s -> %s %d\n", G.vexs[i].data, G.vexs[p->adjvex].data, p->weight);
                break;
            }
            p = p->nextarc;
        }
    }
    printf("\n");
}
/*在D_tabel表中查找没有加入到最短路径集合中最小的值 返回其下标*/
int Search_Min(int size)
{
    int i=0, j=0;
    D_table[0].length = MAX_VALUE;//初始化
    for( i=1; i<=size; ++i )
    {
        if(!D_table[i].style)
        {//表示没有加入到最短路径集合中
            if( D_table[i].length <= D_table[0].length )
            {
                j = i;
                D_table[0].length = D_table[i].length;
            }
        }
    }
    D_table[j].style = 1;//在此处改成 加入到最短路径集合中 状态

    return j;
}

void ShortestPath_DIJ(ALGraph &G, int v0)//v0表示要求的原点在向量表中的下标值
{
    int i=0, j=0;
    for( i=1; i<=G.vexnum; ++i )
    {
        D_table[i].style = 0;//所有的顶点初始化成没有被加入到最短路径集合中
        D_table[i].length = MAX_VALUE;//开始初始化成所有的最短路径为无穷即不可达状态
    }
    D_table[v0].length = 0;//处理开始的顶点 表示最短路径大小值为0  (v0 到 v0)
    for( i=2; i<=G.vexnum; ++i )
    {//根据算法表示要循环 vexnum - 1 次
        j = Search_Min(G.vexnum);//查找最小值 并返回最小值的下标 送j

        for( Arc_Node *p=G.vexs[j].firstarc; p!=NULL; p=p->nextarc )
        {
            if( D_table[p->adjvex].length > D_table[j].length + p->weight )
            {//如果满足修改的条件 则进行修改
                D_table[p->adjvex].length = D_table[j].length + p->weight;
            }
        }
    }
}

void Print_Path( int size)
{
    int i=0;
    for( i=1; i<=size; ++i )
        printf("%d ", D_table[i].length );

    printf("\n");
}
int main()
{
    ALGraph G;

    Create_Graph( G );
    printf("\n");

    Print_Graph( G );

    ShortestPath_DIJ( G, 1);

    Print_Path( G.vexnum );

    return 0;
}

Greate_ALGraph 函数中的
        p1=(Arc_Node*)malloc(sizeof(Arc_Node));
        p1->adjvex=n;    //对弧结点赋邻接点位置信息
        p1->nextarc=G.vexs[i].firstarc;
        G.vexs[i].firstarc=p1
这段应该是错误的 不知道你自己时候测试过  

算法相同的情况下
感觉 这样的代码是想更容易理解点

写的匆忙 没怎么测试

呃，那个还真没注意到
谢谢了，