图论——最短路径-Dijkstra算法和Floyd算法

Dijkstra算法

1.设置三个数组point,visited,MinWeight,visited数组表示元素为1的下标已有最短路径,MinWeight数组表示源点v到各个点的最短路径,point数组表示源点v在访问到各个点前必须访问到的点。

2.首先先将初始时源点v到各个点的值赋值给MinWeight数组,再从中选取最短路径e，将visited数组的源点v值变为1,表明已找到最短路径.将e中的另一个点v'保存后，遍历整个除源点v的其他点vi，如果e的值与v'到vi的距离的和s小于源点v到vi的距离(MinWeight数组保存的数据),则更新MinWeight数组中对应的值和point数组的值

3.将上v‘代入到上个步骤的源点v,重复上个步骤直至图的顶点个数-1次

关于该算法的介绍:   https://blog.csdn.net/heroacool/article/details/51014824

 

void Dijkstra(AMGraph g,int v){
    int visited[g.vecnum];
    int point[maxsize];
    int MinWeight[maxsize];
    for(int i=0;i<g.vecnum;i++)
    {
        MinWeight[i]=g.weight[v][i];
        visited[i]=0;       point[i]=0;
    }
            visited[v]=1;       MinWeight[v]=0;
    int k;
    for(int i=1;i<g.vecnum;i++)
    {
        int minnum=maxnum;
        for(int j=0;j<g.vecnum;j++)
            if(!visited[j]&&minnum>MinWeight[j]){
                k=j;
                minnum=MinWeight[j];
            }
        visited[k]=1;
        for(int j=0;j<g.vecnum;j++)
        if(!visited[j]&&(minnum+g.weight[k][j]<MinWeight[j])){
             MinWeight[j]=minnum+g.weight[k][j];
             point[j]=k;
        }
    }
    for(int i=0;i<g.vecnum;i++)
        cout<<g.point[v]<<"->"<<g.point[i]<<": "<<MinWeight[i]<<endl;
}

Floyd算法

定义两个二维数组,分别存储vi到vj的最短路径和vi到vj必经过的点

void Floyd(AMGraph g){
    int point[g.vecnum][g.vecnum];
    int minweight[g.vecnum][g.vecnum];
    for(int i=0;i<g.vecnum;i++)
        for(int j=0;j<g.vecnum;j++)
        {
            point[i][j]=j;
            minweight[i][j]=g.weight[i][j];
        }
    for(int i=0;i<g.vecnum;i++)
        for(int j=0;j<g.vecnum;j++)
            for(int k=0;k<g.vecnum;k++)
            {
              if(minweight[j][i]+minweight[i][k]<minweight[j][k]){
                    minweight[j][k]=minweight[j][i]+minweight[i][k];
                    point[j][k]=point[j][i];
                }
            }
    for(int i=0;i<g.vecnum;i++)
        for(int j=i+1;j<g.vecnum;j++)
        cout<<"V"<<i<<"->"<<"V"<<j<<"("<<minweight[i][j]<<")"<<endl;
}