单源最短路径Dijkstra算法,和多源最短路径Floyd算法, C++代码

1. 是不是有向图都行,区别只在于邻接矩阵是不是对称矩阵,对算法没有任何影响
2. 边的权重不能为负数

• • 单源最短路径**Dijkstra算法**
  • 多源最短路径**Floyd算法**
  • **例子:**

可以求得单个节点src到所有节点的最短路
按照非递减的顺序找出各个节点的最短路

int Dijkstra(int src, int dest, vector &dist, vector &path, vector> &MAT)
{
    int N = MAT.size();
    if (src < 0 || src >= N)
    {
        cout << "src不在节点0 - (N-1)之间" << endl;
        return -1;
    }
    vector flag(N, false); //标记找到最短路的节点
    //初始化
    for (int i = 0; i < N; i++)
    {
        if (MAT[src][i] != 0)
        {
            dist[i] = MAT[src][i];
            path[i] = src;
        }
    }
    dist[src] = 0;
    flag[src] = true;

    int min_v = -1;
    int min_dis = INT32_MAX;
    while (1)
    {
        min_v = -1;
        min_dis = INT32_MAX;
        //没有找到最短路的flag[i]=false中最小的距离,已经是最短距离了
        for (int i = 0; i < N; i++)
        {
            if (!flag[i])
            {
                if (dist[i] < min_dis) //要带 = 吗????
                {
                    min_dis = dist[i];
                    min_v = i;
                }
            }
        }
        //出口,都找到最短路了
        if (min_v == -1)
            break;

        for (int i = 0; i < N; i++)
        {
            if (MAT[min_v][i] != 0) //有直接相连边
            {
                if (dist[min_v] + MAT[min_v][i] < dist[i]) //更新路径
                {
                    dist[i] = dist[min_v] + MAT[min_v][i];
                    path[i] = min_v;
                }
            }
        }
        flag[min_v] = true;
    }

    //下面这部分只是输出信息了,要不要无所谓
    {
    cout << src << "-" << dest << "最短路径长度为: " << dist[dest] << endl;
    cout<<"路径为: "< PATH;
    int id = dest;
    PATH.push(dest);
    while (path[id] != -1)
    {
        PATH.push(path[id]);
        id = path[id];
    }
    while (!PATH.empty())
    {
        cout << PATH.top() << " ";
        PATH.pop();
    }
    cout << endl;
    }

    return dist[dest];
}

求得所有节点之间的最短路径

//初始化距离矩阵DIST和MAT差不多,对角元素0(自己到自己最短距离),有直接相连的节点初始化为MAT[i][j],没有直接相连的初始化为正无穷INT32_MAX
//path全部是-1
void Floyd(vector>& DIST, vector>& path, vector>& MAT)
{
    int N=MAT.size();
    for(int k=0;k
        for(int i=0;i
            for(int j=0;j
                if(DIST[i][k]+DIST[k][j] >0 && DIST[i][k]+DIST[k][j]0 是因为,但凡有一个是INT32_MAX,结果就是小于0的
                {
                    DIST[i][j]=DIST[i][k]+DIST[k][j];
                    path[i][j]=k;
                }
            }
        }
    }
}

#include 
#include 
#include 
using namespace std;

//单源最短路
int Dijkstra(int src, int dest, vector &dist, vector &path, vector> &MAT);
//多源最短路
void Floyd(vector>& DIST, vector>& path, vector>& MAT);
void print_path(int src, int dest, vector>& path);

int main()
{
    vector> MAT = {{0, 2, 0, 3, 3, 0, 0},
                               {0, 0, 1, 2, 0, 0, 0},
                               {0, 0, 0, 1, 0, 0, 3},
                               {0, 0, 0, 0, 3, 5, 3},
                               {0, 0, 0, 0, 0, 2, 0},
                               {0, 0, 0, 0, 0, 0, 4},
                               {0, 0, 0, 0, 0, 0, 0}};

    int N = MAT.size();
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            MAT[j][i] = MAT[i][j];  //对称矩阵
        }
    }

    //Dijkstra  单源最短路
    int src;
    cout << "输入src:";
    cin >> src;
    int dest;
    cout << "输入dest:";
    cin >> dest;
    vector dist(N, INT32_MAX);
    vector path(N, -1);
    Dijkstra(src, dest, dist, path, MAT);

    //Floyd  多源最短路
    //初始化距离矩阵DIST和MAT差不多,对角元素0(自己到自己最短距离),有直接相连的节点初始化为MAT[i][j],没有直接相连的初始化为正无穷INT32_MAX
    vector> DIST(N,vector(N,INT32_MAX));
    for(int i=0;i
        for(int j=0;j
            if(i==j)
            {
                DIST[i][j]=0;
            }
            else if(MAT[i][j]!=0)
            {
                DIST[i][j]=MAT[i][j];
            }
        }
    }
    vector> floyd_path(N,vector(N,-1));

    Floyd(DIST,floyd_path, MAT);
    // for(int i=0;i
    //     for(int j=0;j
    //         cout<
    //     for(int j=0;j
    //         cout< &dist, vector &path, vector> &MAT)
{
    int N = MAT.size();
    // cout<<"N = "<= N)
    {
        cout << "src不在节点0 - (N-1)之间" << endl;
        return -1;
    }
    vector flag(N, false); //标记找到最短路的节点
    //初始化
    for (int i = 0; i < N; i++)
    {
        if (MAT[src][i] != 0)
        {
            dist[i] = MAT[src][i];
            path[i] = src;
        }
    }
    dist[src] = 0;
    flag[src] = true;

    int min_v = -1;
    int min_dis = INT32_MAX;
    while (1)
    {
        min_v = -1;
        min_dis = INT32_MAX;
        //没有找到最短路的flag[i]=false中最小的距离,已经是最短距离了
        for (int i = 0; i < N; i++)
        {
            if (!flag[i])
            {
                if (dist[i] < min_dis) //要带 = 吗????
                {
                    min_dis = dist[i];
                    min_v = i;
                }
            }
        }
        //出口,都找到最短路了
        if (min_v == -1)
            break;

        for (int i = 0; i < N; i++)
        {
            if (MAT[min_v][i] != 0) //有直接相连边
            {
                if (dist[min_v] + MAT[min_v][i] < dist[i]) //更新路径
                {
                    dist[i] = dist[min_v] + MAT[min_v][i];
                    path[i] = min_v;
                }
            }
        }
        flag[min_v] = true;
    }

    //下面只是输出信息了,要不要无所谓
    cout << src << "-" << dest << "最短路径长度为: " << dist[dest] << endl;
    cout<<"路径为: "< PATH;
    int id = dest;
    PATH.push(dest);
    while (path[id] != -1)
    {
        PATH.push(path[id]);
        id = path[id];
    }
    while (!PATH.empty())
    {
        cout << PATH.top() << " ";
        PATH.pop();
    }
    cout << endl;

    return dist[dest];
}

//初始化距离矩阵DIST和MAT差不多,对角元素0(自己到自己最短距离),有直接相连的节点初始化为MAT[i][j],没有直接相连的初始化为正无穷INT32_MAX
//path全部是-1
void Floyd(vector>& DIST, vector>& path, vector>& MAT)
{
    int N=MAT.size();
    for(int k=0;k
        for(int i=0;i
            for(int j=0;j
                if(DIST[i][k]+DIST[k][j] >0 && DIST[i][k]+DIST[k][j]0 是因为,但凡有一个是INT32_MAX,结果就是小于0的
                {
                    DIST[i][j]=DIST[i][k]+DIST[k][j];
                    path[i][j]=k;
                }
            }
        }
    }
}

void print_path(int src, int dest, vector>& path)
{
    if(path[src][dest]==-1) //中间谁都不隔
    {
        cout<