欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图论(最短路径,Dijkstra算法和Floyd算法)

程序员文章站 2022-04-30 09:17:59
...
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;

#define maxSize 101

int INF = -2313;
int MINF = 6666;//定义图的图的无穷大量

typedef struct MGraph
{
    int n,e;
    int edges[maxSize][maxSize];
};


//邻接表
typedef struct ArcNode
{
    int adjvex;//该点所指顶点的位置信息

    ArcNode *nextarc;//指向下一条边
} ArcNode;

typedef struct
{

    int data;
    int count;//统计入度信息
    ArcNode *firstarc;//指向第一条边


} VNode,AdjList;

typedef struct AGraph
{
    AdjList adjlist[maxSize];

    int n,e;

} AGraph;

int visit[1001];


//邻接矩阵转化为邻接表
void creatAGraph(AGraph *G,MGraph M)
{

    G->e = M.e;
    G->n = M.n;



    for(int i=0; i<M.n; i++) //构造顶点表
    {
        G->adjlist[i].data = i;
        G->adjlist[i].firstarc = NULL;
        G->adjlist[i].count = 0;
    }


    ArcNode *p;



    for(int i=0; i<M.n; i++) //头插法来构造
    {
        for(int j=0; j<M.n; j++)
            if(M.edges[i][j]!=0)//当存在边的时候采用头插法来构造
            {
                p = (ArcNode*)malloc(sizeof(ArcNode));

                p->adjvex = j;


                p->nextarc = G->adjlist[i].firstarc;


                G->adjlist[i].firstarc = p;


                G->adjlist[j].count++;//对应的入度加1

            }
    }//end for
}


void Visit(int v)
{
    printf("->%d",v);
}

//Dijkstra最短路径
//单源最短路径
/*
    M
    v 访问的起点
    dist 路径数组
    path 记录该节点的前驱结点信息
*/
void Dijkstra(MGraph M,int v,int dist[],int path[])
{
    int i,j,u;//u保存存放的结点信息
    int vset[maxSize];//访问标记数组
    int min;


    //初始化
    for(i=0;i<M.n;i++)
    {
        dist[i] = M.edges[v][i];
        vset[i] = 0;//标记改结点未访问

        if(M.edges[v][i] != 0)//在最短路径中的节点
            path[i] = v;
        else
            path[i] = -1;

    }//end for

    path[v] = -1;

    vset[v] = 1;//标记起点访问过

    //对剩余n-1个结点并入最短路径中
    for(i=0;i<M.n-1;i++)
    {

        //从当前选出最短路径
        min =MINF;//重置最小值

        for(j=0;j<M.n;j++)
            if(vset[j] == 0&&dist[j]<min)//当该节点未访问,并且最小选出该结点将其并入最短路径中
            {
                min = dist[j];
                u = j;
            }

        vset[u] = 1;//将选出当前权值最小的结点并入最短路径中

        //更新path和dist

        for(j=0;j<M.n;j++)
            if(vset[j] ==0&&M.edges[u][j]+dist[u]<dist[j])//当以该节点作为起始结点到j的距离与dist数组作比较
            {
                dist[j] = dist[u] + M.edges[u][j];

                path[j] = u;//记录j的在最短路径上的前驱结点为u
            }



    }//end for


}//end Dijkstra

//打印当前最短路径的信息
void printPath_Dijkstra(int path[],int a)
{
    stack<int> S;

    while(path[a] != -1)
    {
        S.push(a);
        a = path[a];
    }

    S.push(a);//将根节点入栈

    while(!S.empty())
    {
        printf("%d->",S.top());
        S.pop();
    }

    printf("\n");
}


/*
    Floyd 所有顶点的最短路径(任意两点之间的最短路径问题)

    path[][]用来记录两结点之间中间结点的信息

    A[][] 数组存放任意两结点之间最路径的长度

*/
void Floyd(MGraph M,int path[][maxSize],int A[][maxSize])
{
    int k;//k为中间结点
    int i,j;

    //初始化数据
    for(i=0;i<M.n;i++)
        for(j=0;j<M.n;j++)
        {
            A[i][j] = M.edges[i][j];

            path[i][j] = -1;
        }

    for(k=0;k<M.n;k++)//依次遍历每个中间结点
        for(i=0;i<M.n;i++)
            for(j=0;j<M.n;j++)
                if(A[i][j]>A[i][k]+A[k][j])//当从i到j的路径长度大于经过中间结点k时则更新A[][]
                {
                    A[i][j] = A[i][k] + A[j][k];
                    path[i][j] = k;
                }

}//end Floyd


//输出从v到u的路径
//递归算法
void printPath_Floyd(int u,int v,int path[][maxSize])
{

    if(path[u][v] == -1)//从u->v为直接的一条边,直接输出
        printf("%d->%d\n",u,v);

    else{
        int mid = path[u][v];
        printPath_Floyd(u,mid,path);//递归调用从u到mid(中间结点)

        printPath_Floyd(mid,v,path);//递归调用从mid(中间结点)到v
    }


}//end printPath_Floyd