带权单源最短路发[稠密图]（Dijkstra）

对于稠密图，采用邻接矩阵较为合适

所以我们先构建一个邻接矩阵

typedef int Vertex;

typedef int WeightType;

//图

typedef struct MyGraph

{

    int v, e;

    WeightType G[MaxVertexNum][MaxVertexNum];

}MyGraph;

//顶点信息， 可以不定义

typedef struct NodeType

{

    Vertex id;

//    Data data;            当节点有需要添加的信息时使用

}NodeType;

接下来我们使用Dijkstrs算法

void Dijkstra(int dist[], Vertex path[], MyGraph& g, Vertex id)

{

        //是否被收入的集合

    int collection[g.v];

    memset(collection, , sizeof(collection));

    dist[id] = ;

    int mmin = INF;

    while()

    {

        int v = -;

        mmin = INF;

        //稠密图用循环选出还没加入的节点的暂时的最短路的最小值

        for(int i = ; i < g.v; i++)

            if(mmin > dist[i] && collection[i] != )

            {

                mmin = dist[i];

                v = i;

            }

        //如果都加入了， 那么退出

        if(v == -)

            break;

        //将选出的节点收入

        collection[v] = ;

        //修改因为收入节点而受影响的节点的最短路

        for(int j = ; j < g.v; j++)

        {

            //如果使得原来的节点变得更短， 则更新最短距离并且更新最短路

            //这里collection[j]要没有被收入才计算，

            //因为如果j被收入，那么dist[v]应当更小，那么v应当在j之前被收入， 相互矛盾

            if(collection[j] ==  && dist[j] > dist[v] + g.G[v][j])

            {

                dist[j] = dist[v] + g.G[v][j];

                path[j] = v;

            }

        }

    }

} 

新手，欢迎大家找错误，提建议