Prim & Dijkstra & Floyd 算法实现、联系与区别 && 使用Floyd算法求次短路径

目录

文章目录

• Prim & Dijkstra & Floyd 算法实现、联系与区别 && 使用Floyd算法求次短路径
• • • • 目录
      • 掏心窝子
      • 基础知识
      • 算法详解
      • • 一、Prim算法
        • • 1、文字描述
          • 2、结构确定
          • 3、过程演示
          • 4、代码解析
          • 5、运行结果
        • 二、Dijkstra算法
        • • 1、文字描述
          • 2、结构确定
          • 3、过程演示
          • 4、代码解析
          • 5、运行结果
        • 三、Floyd算法
        • • 1、数据结构
          • 2、代码简析
      • 算法异同
      • Floyd算法求次短路径

掏心窝子

主要还是因为我本来想在极短的复习时间内用CSDN搞个算法速成，但是同一篇文章被不停地转载搬运，一大堆引流营销号在水文章，导致了网上搜算法解析的效率还没有自己看书高，间接导致了考试翻车。这谁能忍？只好自己写一篇大杂烩让后来者不要因为优质内容太少而跳进我跳进过的坑里

基础知识

First of all，Prim 和 Dijkstra算法都有同一个理论基础-- --MST性质，大意是 **假设有一个连通网络，所有节点组成一个集合G，对G的一个真子集U，如果一条边E是 满足“一个端点在U中，另一个端点在G中但不在U中”条件 的边里最短的一条，那么一定存在G的一棵最小生成树包含边E。**我的数学不好，这里就不给大家证明了。

算法详解

一、Prim算法

1、文字描述

从任意一个顶点开始，首先把这个顶点加入到生成树T中，然后在所有一个端点在树中，一个端点不在树中的边里选择一条长度最短的，然后把这条边和边对应的节点加入生成树，依此类推，直到把所有的节点都加入生成树。

2、结构确定

确定有关的储存结构

struct edge
{
	int vi, vj;  // 边的起点和终点
	int weight;  // 权重
};

int w_matrix[n][n];  // 邻接矩阵
edge T[n - 1];  // 记录最小生成树

3、过程演示

4、代码解析

void prim(edge T[6])  //
{
	int m, v, min;
	edge e;

	// 初始化边数组
	for (int i = 1; i < 6; i++)
	{
		T[i - 1].vi = 1;
		T[i - 1].vj = i + 1;
		T[i - 1].weight = w_mtx[0][i];
	}

	//求第 i + 1 条最小生成树的边
	for (int i = 0; i < 5; i++)  // 最小生成树一共有 6 - 1 = 5 条边
	{
		min = INFI;
		//在 T[i] 到 T[n - 2]中选择权值最小的边加入最小生成树
		for (int j = i; j < 5; j++)
		{
			if (T[j].weight < min)
			{
				min = T[j].weight;
				m = j;
			}
		}
		//把选出来的权值最短的边移到最前面
		e = T[m]; T[m] = T[i]; T[i] = e;
		//此时新加入的边对应的顶点序号
		v = T[i].vj;
		//更新边表，在上图的例子中就是把V1-Vn长度与V3-Vn的值进行比较
		//这样的话，表中保存的始终就是一个端点在集合内，一个端点在集合外的边中最短的几条
		int d = 0;
		for (int k = i + 1; k < 5; k++)
		{
			d = w_mtx[v - 1][T[k].vj - 1];
			if (d < T[k].weight)
			{
				T[k].weight = d;
				T[k].vi = v;
			}
		}
	}

}

5、运行结果

二、Dijkstra算法

1、文字描述

方法的基本操作是：将图的顶点集合V分成A、B两组，其中原点到A组中的顶点的最短路径已确定，B组的顶点未确定。初始时A中只有起点，随后从B中选出距离起点最近的节点加入A。此时，对边表进行更新：以新加入节点作为起点，遍历新节点到B中所有其他节点的距离，寻找与它相邻的点中路径最短的点，如后把这个点也加入集合A中，直到所有的节点都进入A中。

2、结构确定

确定有关的储存结构

struct path
{
	int pre;  // 前一个被加入A的节点
	int length;  // 权重
};

int w_mtx[n][n];  // 邻接矩阵
path dist[];  // 记录最小路径树

3、过程演示

4、代码解析

这里用了另一个更能体现Dijkstra算法区别于Prim算法的用例，这两种算法的区别我会在后面的文章中详细分析

void dijkstra(path dist[], int s) //s为原点序号
{
	int i, u, min;
  	// 初始化dist数组
	for(i = 0; i < 5; i++)
	{
		dist[i].length = w_mtx[s][i];
		if (dist[i].length == INFI)
		{
			dist[i].pre = -1;
		}
		else
		{
			dist[i].pre = s;
		}
	}

	w_mtx[i][i] = 1;  // 标记已经加入A的节点

	//按顺序把节点加入A
	while (1)
	{
		u = -1;
		min 5、 INFI;
		for (i = 0; i < 5; i++)
		{
			if (w_mtx[i][i] == 0 && dist[i].length < min)
			{
				min = dist[i].length;
				u = i;
			}
		}
        
		if (u == -1)
		{
            // 如果所有的节点都已加入A(w_mtx[i][i]=0)，
        	// 或者剩下的节点都不可达(dist[i].length=INFI)，
        	// 则结束算法
			cout << "NO MORE VERTEX CAN BE ADD INTO A FROM B" << endl;
			return;
		}
		w_mtx[u][u] = 1;
		//更新距离
		for (i = 0; i < 5; i++)
		{
			if (w_mtx[i][i] == 0 && dist[i].length > dist[u].length + w_mtx[u][i])
			{
				dist[i].length = dist[u].length + w_mtx[u][i];
				dist[i].pre = u;
			}
		}
	}

}

5、运行结果

三、Floyd算法

这个算法我在网上找到了一篇非常详细的教程，写的简洁明了，这里决定专业的事情让更专业的人去做，把链接展示如下：

傻子也能看懂的弗洛伊德算法(转)

这篇文章我找不到原博客了，我也不确定上面的那个链接是不是原博，总之上面那篇是在百度搜索里发布时间最早的一篇，将就着看吧，只是苦了原作者了。

感受一下目前互联网令人窒息的转载风气

下面贴出我的代码：

1、数据结构

说明：这里我引入了一个path矩阵，用于储存路径，因为上文作者的算法只会输出最短距离，没法知道路径

int path[n][n];

储存规则：假如w_matrix中的数据被修改了，同时修改path对应位置的数据为上一节点的编号

2、代码简析

以下为伪代码

#define INFI 10000 

int path[n][n];
void Floyd(int D[n][n], int w_mtx[n][n])
{
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(w_mtx[i][j] != INFI) path[i][j] = i + 1;
			else path[i][j] = 0;
			D[i][j] = w_mtx[i][j];
		}
		for(int k = 0; k < n; k++)
		{
			for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
				{
					if(D[i][j] > D[i][k] + D[k][j])  // 核心代码
					{
						D[i][j] = D[i][k] + D[k][j];
						path[i][j] = path[k][j];  // 更新path
					}
				}
			}
		}
	}
}

算法异同

找到一篇写的挺好的文章讲清楚了这个问题

省流:

Prim算法用于构建最小生成树——即树中所有边的权值之和最小。例如，构建电路板，使所有边的和花费最少。只能用于无向图。

Dijkstra算法用于构建单源点的最短路径树(MST)——即树中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是不能存在负权值(Bellman-Ford可以处理负权值)。

Floyd算法求次短路径

某个ACM大佬同学写的

#include<iostream>
#include<cstdio>
#include<stack>
#define ma 100000000
using namespace std;
stack<int> out;
int n, adj[35][35][2], path[35][35][2];
void floyd_change()
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i == k || j == k)
                    continue;
                int a, b;
                if((adj[i][k][0] + adj[k][j][0]) < adj[i][j][0])
                {
                    adj[i][j][1] = adj[i][j][0];
                    path[i][j][1] = path[i][j][0];
                    adj[i][j][0] = adj[i][k][0] + adj[k][j][0];
                    path[i][j][0] = path[k][j][0];
                    if((adj[i][k][0] + adj[k][j][1]) < (adj[i][k][1] + adj[k][j][0]))
                    {
                        a = 0;
                        b = 1;
                    }
                    else
                    {
                        a = 1;
                        b = 0;
                    }
                    if((adj[i][k][a] + adj[k][j][b]) < adj[i][j][1])
                    {
                        adj[i][j][1] = adj[i][k][a] + adj[k][j][b];
                        path[i][j][1] = path[k][j][b];
                    }
                }
                else if((adj[i][k][0] + adj[k][j][0]) < adj[i][j][1] && path[k][j][0] != path[i][j][1])
                {

                    adj[i][j][1] = adj[i][k][0] + adj[k][j][0];
                    path[i][j][1] = path[k][j][0];
                }
            }
        }
    }
}
int main()
{
    cout << "请输入结点数\n";
    cin >> n;
    cout << "请输入相邻矩阵，正无穷使用-1表示，其他路径必须小于100000\n";
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            scanf("%d", &adj[i][j][0]);
            if(adj[i][j][0] == -1)
                adj[i][j][0] = ma;
            adj[i][j][1] = ma;
            path[i][j][0] = i;
            path[i][j][1] = -1;
        }
    }
    floyd_change();
    cout << "请依次输入每轮查询的路径起点与终点，起点与终点都为-1时结束查询\n";
    int a, b;
    while(cin >> a >> b)
    {
        if(a == -1 && b == -1)
            break;
        cout << "接下来第一行为最短路径长度及路径，第二行为次短路径长度与路径(-1代表无路径):\n";
        if(adj[a][b][0] == 100000000)
            cout << -1 <<endl;
        else
        {
            cout << adj[a][b][0] << " : ";
            int tmp = b;
            while(tmp != a)
            {
                out.push(tmp);
                tmp = path[a][tmp][0];

            }
            out.push(a);
            while(out.size())
            {
                cout << out.top() << " ";
                out.pop();
            }
            cout << endl;
        }
        if(adj[a][b][1] == 100000000)
            cout << -1 <<endl;
        else
        {
            int f = 0;
            cout << adj[a][b][1] << " : ";
            int tmp = b;
            out.push(b);
            while(tmp != a)
            {
                if(path[a][tmp][1] != path[a][tmp][0] && !f)
                {
                    f = 1;
                    tmp = path[a][tmp][1];
                }
                else
                    tmp = path[a][tmp][0];
                out.push(tmp);
            }
            if(tmp == a && path[a][tmp][1] != a && !f)
            {
                tmp = path[a][tmp][1];
                out.push(tmp);
                while(tmp != a)
                {
                    tmp = path[a][tmp][0];
                    out.push(tmp);
                }
            }
            while(out.size())
            {
                cout << out.top() << " ";
                out.pop();
            }
            cout << endl;
        }
    }
    return 0;
}