最短路算法包
标签： ACM 最短路
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<iomanip>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<functional>
#define INF 99999
using namespace std;
typedef pair<int, int> P;
struct edge {
int from, to, cost;
};
int n, m; //n为顶点数，m为边数
int a[100][100];
void warshall()
{
int b[100][100] = { 0 };
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
b[i][j] = a[i][j];
cout << "Floyd-warshall:
";
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
if (b[j][k] > b[j][i] + b[i][k])
{
b[j][k] = b[j][i] + b[i][k];
}
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cout << b[i][j] << " ";
}
cout << endl;
}
}
void Dijkstra()
{
int dis[100] = { 0 };
bool book[100] = { 0 };
int b[100][100] = { 0 };
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
b[i][j] = a[i][j];
for (int i = 1; i <= n; i++)
{
dis[i] = a[1][i];
}
book[1] = 1;
for (int i = 1; i <= n - 1; i++)
{
int minv = INF, min = 0;
for (int i = 1; i <= n; i++)
{
if (!book[i] && minv > dis[i])
{
minv = dis[i]; //在取最小值的过程中可以用堆优化
min = i;
}
}
book[min] = 1;
for (int j = 1; j <= n; j++)
{
if (dis[j] > dis[min] + a[min][j])
{
dis[j] = dis[min] + a[min][j]; //用最短的边对其他所有点进行优化
}
}
}
for (int i = 1; i <= n; i++)
{
cout << dis[i] << " ";
}
cout << endl;
}
void Bellman()
{
int dis[100] = { 0 };
int b[100][100] = { 0 };
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
b[i][j] = a[i][j];
for (int i = 1; i <= n; i++)
dis[i] = INF;
dis[1] = 0;
/*for (int i = 1; i <= n; i++)
{
dis[i] = a[1][i];
}*/
for (int i = 1; i <= n - 1; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
if (dis[k] > dis[j] + a[j][k])
{
dis[k] = dis[j] + a[j][k];
}
}
}
}
for (int i = 1; i <= n; i++)
{
cout << dis[i] << " ";
}
cout << endl;
}
void BellmanQueue()
{
int dis[100] = { 0 };
int b[100][100] = { 0 };
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
b[i][j] = a[i][j];
for (int i = 1; i <= n; i++)
dis[i] = INF;
dis[1] = 0;
queue<int> que;
bool book[100] = { 0 };
que.push(1);
book[1] = 1;
while (que.size())
{
int k = que.front();
que.pop();
for (int i = 1; i <= n; i++)
{
if (dis[i] > dis[k] + b[k][i])
{
dis[i] = dis[k] + b[k][i];
if (!book[i])
{
que.push(i);
book[i] = 1;
}
}
}
book[k] = 0;
}
for (int i = 1; i <= n; i++)
{
cout << dis[i] << " ";
}
cout << endl;
}
void warshall2()
{
vector<edge> G[100];
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int p;
edge q;
cin >> p >> q.to >> q.cost;
G[p].push_back(q);
}
for (int i = 1; i <= n; i++)
{
for (int k = 1; k <= n; k++)
{
for (int j = 0; j < G[k].size(); j++)
{
edge e = G[k][j];
}
}
}
cout << "不会
";
}
void Dijkstra2()
{
vector<edge> G[100];
int n, m;
cin >> n >> m;
int dis[100] = { 0 };
fill(dis, dis + 100, INF);
dis[1] = 0;
for (int i = 0; i < m; i++)
{
int p;
edge q;
cin >> p >> q.to >> q.cost;
G[p].push_back(q);
}
priority_queue<P, vector<P>, greater<P> >que;
que.push(P(0, 1));
while (que.size())
{
P p= que.top(); que.pop();
for (int i = 0; i < G[p.second].size(); i++)
{
edge e = G[p.second][i];
if (dis[e.to] > dis[p.second] + e.cost)
{
dis[e.to] = dis[p.second] + e.cost;
que.push(P(dis[e.to], e.to));
}
}
}
for (int i = 1; i <= n; i++)
{
cout << dis[i] << " ";
}
cout << endl;
}
void Bellman2()
{
edge G[100];
int n, m;
cin >> n >> m;
int dis[100] = { 0 };
fill(dis, dis + 100, INF);
dis[1] = 0;
for (int i = 0; i < m; i++)
{
cin >> G[i].from >> G[i].to >> G[i].cost;
}
for (int i = 1; i <= n - 1; i++)
{
for (int j = 0; j < m; j++)
{
dis[G[j].to] = min(dis[G[j].to], dis[G[j].from] + G[j].cost);
}
}
for (int i = 1; i <= n; i++)
{
cout << dis[i] << " ";
}
cout << endl;
}
int main()
{
cin >> n >> m;
for(int i=0;i<=n;i++)
for (int j = 0; j <= n; j++)
{
if (i == j) a[i][j] = 0;
else a[i][j] = INF;
}
for (int i = 1; i <= m; i++)
{
int p, q, t;
cin >> p >> q >> t;
a[p][q] = t;
}
cout << "邻接矩阵:
";
cout << "1:Floyd-warshall 2:Dijkstra 3:Bellman-Ford 4:Bellman队列优化(SPFA)
";
cout << "邻接表
";
cout << "5:Floyd-warshall 6:Dijkstra(堆优化) 7：Bellman-Ford
";
int t;
while (cin >> t)
{
if (t == 1)
{
warshall();
}
else if (t == 2)
{
cout << "Dijkstra:
";
Dijkstra();
}
else if (t == 3)
{
cout << "Bellman-Ford:
";
Bellman();
}
else if (t == 4)
{
cout << "Bellman队列优化:
";
BellmanQueue();
}
else if (t == 5)
{
cout << "Floyd-warshall（邻接表）:
";
warshall2();
}
else if (t == 6)
{
cout << "Dijkstra(堆优化)
";
Dijkstra2();
}
else if (t == 7)
{
cout << "Bellman-Ford:
";
Bellman2();
}
}
}