最短路径算法题总结

单源最短路径——Dijkstra

时间复杂度：O(n^2)
贪心算法
当图中存在负权值时不适用，改用Folyd

for循环
{
选出最近的点，把该点加入集合
计算从该点出发到其他所有点的距离（排除集合中的点）并更新距离
}

#include
using namespace std;
#define inf 0x3f3f3fint n, s, e; //n为点的个数，s，e分别为起点终点
int mmap[1000][1000]; //各点之间的距离，若为无向图则对称
int dis[1000], sset[1000] = {0}; //dis为到原点的距离，sset为该点是否加入集合
vector<int> path[1000];  //path为各点到原点的最短路径void dij(){for(int i=0; i<n; i++){dis[i] = inf;  }dis[s] = 0;path[s].push_back(s);for(int i=0; i<n; i++){int mmin = inf;int now;for(int j=0; j<n; j++){if(dis[j] < mmin && sset[j] == 0){mmin = dis[j];now = j;}}sset[now] = 1;for(int j=0; j<n; j++){if(sset[j] == 0 && (dis[now] + mmap[now][j] < dis[j])) {dis[j] = dis[now] + mmap[now][j];path[j] = path[now];path[j].push_back(j);}}}
}int main(){cin >> n;for(int i=0; i<n; i++)for(int j=0; j<n; j++)mmap[i][j] = inf;for(int i=0; i<n; i++)for(int j=0; j<n; j++){cin >> mmap[i][j];if(mmap[i][j] == 100)mmap[i][j] = inf;}cin >> s >> e;dij();cout << dis[e] << endl;for(int i=0; i<path[e].size() - 1; i++)cout << path[e][i] << "->";cout << path[e][path[e].size() - 1] << endl;
}

全对最短路径——Floyd

时间复杂度: O(n^3)
贪心算法
适用于图中含有正、负权值

步骤：
1⃣️初始化map矩阵
矩阵中map[i][j]的距离为顶点i到顶点j的权值；

如果i和j不相邻，则map[i][j]=∞。
如果i==j，则map[i][j]=0;

2⃣️以顶点A(假设是第k个顶点)为中介点，若a[i][k]+a[k][j] < a[i][j]，则设置a[i][j]=a[i][1]+a[1][j]。

#include
using namespace std;
#define inf 0x3f3f3fint n, s, e; //n为点的个数，s，e分别为起点终点
int mmap[1000][1000]; //各点之间的距离，若为无向图则对称
int path[1000][1000]; //path为i,j之间的点void floyd(){for(int i=0; i<n; i++)for(int j=0; j<n; j++){path[i][j] = -1;}for(int k=0; k<n; k++){for(int i=0; i<n; i++){for(int j=0; j<n; j++){if(mmap[i][k] + mmap[k][j] < mmap[i][j]){mmap[i][j] = mmap[i][k] + mmap[k][j];path[i][j] = k;}}}}
}int main(){cin >> n;for(int i=0; i<n; i++)for(int j=0; j<n; j++)mmap[i][j] = inf;for(int i=0; i<n; i++)for(int j=0; j<n; j++){cin >> mmap[i][j];if(mmap[i][j] == 100)mmap[i][j] = inf;}cin >> s >> e;floyd();cout << mmap[s][e] << endl;cout << s << " ";vector<int> dis;int k = path[s][e];while(k != -1){dis.push_back(k);k = path[s][k];}for(int i=dis.size()-1; i>=0; i--)cout << dis[i] << " ";cout << e << endl;
}

SPFA

可以解决带有负权边，负环的问题
例题可参考

https://blog.csdn.net/pursue_my_life/article/details/80201499

初始化代码

void init()
{memset(vis, false, sizeof(vis));  //将vis[]数组置为0memset(money, false, sizeof(money));  //将money[]数组置为0for(int i = 0; i < maxn; ++i)memset(cost[i], false, sizeof(cost[i]));  //将cost[][]二维数组置为0fill( dis, dis+maxn, inf);  //将dis数组置为inf
}

memset和fill的区别与使用方法

memset：按照字节填充某字符

#include 
const int INF = 0x3f3f3f3f;
memset(a,INF,sizeof(a));

fill：按照单元赋值，将一个区间的元素都赋予val值

#include 
fill(vec.begin(), vec.end(), val); //容器vector
fill(dis, dis+maxn, inf); //一维数组

因为memset函数按照字节填充，所以一般memset只能用来填充char型数组，（因为只有char型占一个字节）。如果填充int型数组，只能填充0、-1 和 inf（正负都行）。因为00000000 = 0，-1同理，如果我们把每一位都填充“1”，会导致变成填充入“11111111”。如果我们将inf设为0x3f3f3f3f，0x3f3f3f3f的每个字节都是0x3f！所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。无穷小可以将-INF设为0x8f。
而fill函数可以赋值任何值

memset比fill处理速度快一些，所以在能满足需要时，推荐用memset

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！