无权图的最短路径算法

佚名 6年前 (2019-04-19) 随笔 1016人围观抢沙发百度已收录

邻接矩阵版

先构造邻接矩阵

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

typedef int Vertex;

typedef struct MyGraph
{
    int v, e;                //顶点数， 边数 
    Vertex G[MaxVertexNum][MaxVertexNum];            //邻接矩阵 
}MyGraph;

单源无权最短路算法

//单源无权最短路 
//dist[i]保存顶点id到顶点i的最短距离
//path[i]保存id到i的最短路的前一个顶点， 最后可通过逆序打印将id到每一个顶点的最短路径打印出来

void NoWeightShortestPath(int dist[], Vertex path[], MyGraph& g, Vertex id)
{ 
    Queue q;        //自己实现的队列
    q.push(id);
    dist[id] = 0;
    
    while(!q.empyt())
    {
        Vertex p =     q.pop();
        for(int i = 0; i < g.v; i++)
        {
            if(g.G[p][i] == 1 && dist[i] == -1)
            {
                path[i] = p;
                dist[i] = dist[p] + 1;
                q.push(i);
            }
        }
    }    
}