图论

公开的图书评论利于形成社区讨论 #生活乐趣# #读书乐趣# #图书评论#

最短路径问题

1 Floyed

穷举所有中间点k，如果i到j到距离大于i到k的距离 + k到j的距离，则刷新

if(a[i][j]>a[i][k]+a[k][j])

   a[i][j] = a[i][k] + a[k][j];

#include <iostream>

using namespace std;

const int MAX = 99999999;

int n, m;

int a[1001][1001];

void floyd() {

for(int k=1; k<=n; k++) {

for(int i=1; i<=n; i++) {

for(int j=1; j<=n; j++) {

if(a[i][j]>a[i][k]+a[k][j])

a[i][j] = a[i][k] + a[k][j];

}

}

}

for(int i=1; i<=n; i++) {

for(int j=1; j<=n; j++) {

cout << i << " -> " << j << " : " << a[i][j] << endl;

}

cout << endl;

}

}

void read() {

int x, y, w;

cin >> n >> m;

for(int i=1; i<=n; i++)

for(int j=1; j<=n; j++) a[i][j] = MAX;

for(int i=1; i<=n; i++) a[i][i] = 0;

for(int i=1; i<=m; i++) {

cin >> x >> y >> w;

a[x][y] = w;

}

}

int main() {

read();

floyd();

return 0;

}

2 Dijkstra

Dijkstra 单源最短路径（源点到其他点的最短距离）

数组 D[i]表示源点(s)到i的最短距离

有两个集合：

S(求出最短距离的点)、T（未求出最短距离的点）

S初始时为空

1> 初始化：(最短距离=直接距离)

D[1~n] = a[s][i];

（D[s] = 0）

2> j=1~n;找d[j]的最小值，如果不在S中，记下其下标K，把k加入S;

3>用k作为中间点刷新;做2> n-1次，把所有点加到S中

#include <iostream>

using namespace std;

const int MAX = 999999999;

int n, m, s;

int a[1001][1001];

int d[1001];

bool InS[1001];

void read() {

int x, y, w;

cin >> n >> m >> s;

for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) a[i][j] = MAX;

for(int i=1; i<=n; i++) a[i][i] = 0;

for(int i=1; i<=m; i++) {

cin >> x >> y >> w;

a[x][y] = w;

}

}

int Dijkstra(int x) {

int min, k;

for(int i=1; i<=n; i++) d[i] = a[x][i];

d[x] = 0;

InS[x] = true;

for(int i=1; i<=n-1; i++) {

min = MAX;

for(int j=1; j<=n; j++) {

if(min > d[j] && !InS[j]) {

min = d[j];

k = j;

}

}

InS[k] = true;

for(int j=1; j<=n; j++) {

if(d[j] > d[k]+a[k][j]) {

d[j] = d[k] + a[k][j];

}

}

}

for(int i=1; i<=n; i++) cout << d[i] << " ";

}

int main() {

read();

Dijkstra(s);

return 0;

}

3 SPFA(单源最短路径)

SPFA可以处理负权(不能处理负权的环)，利用队列实现

同Dijkstra，D[i]表示源点(s)到i的最短距离

初始化：

D[1~n] = MAX， D[s] = 0;

1> 把源点入队列，当队列不为空时，循环出队列

2> 顶点K出队列,通过K刷新最短距离

如果D[j]被刷新，判断j是否在队列中，不在则入队列

利用C++ STL<queue>解：

#include <iostream>

#include <queue>

using namespace std;

const int MAX = 999999999;

int n, m, s;

int a[1001][1001];

int d[1001];

bool inq[1001];

queue<int> q;

void read() {

int x, y, w;

cin >> n >> m >> s;

for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) a[i][j] = MAX;

for(int i=1; i<=n; i++) a[i][i] = 0;

for(int i=1; i<=m; i++) {

cin >> x >> y >> w;

a[x][y] = w;

}

}

void SPFA(int x) {

int k;

for(int i=1; i<=n; i++) d[i] = MAX;

d[x] = 0;

q.push(x);

inq[x] = true;

while(!q.empty()) {

k = q.front();

q.pop();

inq[k] = false;

for(int j=1; j<=n; j++) {

if(a[k][j] == MAX) continue;

if(d[j] > d[k]+a[k][j]) {

d[j] = d[k]+a[k][j];

if(!inq[j]) {

q.push(j);

inq[j] = true;

}

}

}

}

for(int i=1; i<=n; i++) cout << d[i] << " ";

}

int main() {

read();

SPFA(s);

return 0;

}

^_#

网址：图论 https://www.yuejiaxmz.com/news/view/494071

相关内容

柏拉图与古典幸福论研究
二手图书交易平台论文
CNCC2018 分论坛(10) | 知识图谱＋数字经济＝？
低碳生活绿色发展论文1000字高清大图
从“理念论”到“目的论”——亚里士多德对柏拉图“至善”观的批评与超越
科学网—论文投稿可编辑图片如何解决？
供热的基本理论及水压图(1).pdf
基于spring boot的图书馆图书借阅管理系统设计与实现【毕业设计+论文】
河北二手旧书回收图书以质论价
读者对美食类图书的需求现状分析,硕士论文

随便看看