图最短路径算法

- 迪杰斯特拉算法
- 弗洛伊德算法
- BFS

迪杰斯特拉算法

求原点0到其他点的最短路径
在这里插入图片描述

#include<iostream>
#include<vector>
#include<string.h>
#define N 10
#define INF 65535
using namespace std;

int graph[N][N];
int dist[N];
int parent[N];

// 迪杰斯特拉算法 
/*
找出源点到其他点的最短路径
核心思想：
	节点集合V, 已经被访问（找到最短路径）的集合S，和未被访问的集合W
	1.每次从W中找到一个距离S最近的点v1 (visited[v1] = false && dist[v1] < INF),  
	2.将v1 加入到集合S中，即visited[v1] = true
	3. 更新以v1为中转点， start -> ... -> v1 -> w w∈W的距离
		if (!visited[w] && (graph[v1][w] + dist[v1] < dist[w]) dist[w] = dist[v1] + graph[v1][w] 
	4. 循环n-1次，直到S中包含了所有节点，即W集合变为空集 
	
体现的是贪心思想： 每次从 W集合中找到一个离S最近的点w
	时间复杂度O(n^2)  
*/ 

int *dijkstra(int v0, int n) {
	//是否被访问数组
	bool visited[N] = {false}; 
	//距离数组
	//初始被访问节点 
	dist[v0] = 0;
	visited[v0] = true;
	int v1 = v0;
	parent[v0] = -1;
	//遍历其余n-1个点 
	for (int i = 1; i < n; i++) {
		int mind = INF;
		//找距离集合S（已经被访问） 最近的一个未被访问的点 
		for (int j = 0; j < n; j++) {
			// 核心过程--选点, 如果j在{V}-{S}中 
			if (!visited[j]) { 
				if (dist[j] < mind) {
					mind = dist[j];
					v1 = j;
				}
			}
		}
		//将v1点加入到被访问的集合S中 
		visited[v1] = true;
		// 更新以v1为中转点的节点的距离 
		for (int i = 0; i < n; i++) {
			if (!visited[i] && (dist[i] > dist[v1] + graph[v1][i])) {
				dist[i] = dist[v1] + graph[v1][i];
				parent[i] = v1;
			}
		} 
	}
	return dist; 
}

int main() {
	int ne = 10, nv = 6;
	int edges[][3] = {{0,1,2},{0,2,5},{1,2,1},{1,3,3},{2,3,3},{2,4,4},{2,5,1},{3,4,1},{3,5,4},{4,5,1}};
	
	//二维整型数组直接利用 memset() 函数初始化时，只能初始化为 0 或 -1 ，否则将会被设为随机值
	//手动初始化 
	for (int i = 0; i < nv; i++) {
		dist[i] = INF;
		for (int j = 0; j < nv; j++) {
			graph[i][j] = INF;
		}
	}
	//初始化边 
	int start = 0;
	for (int i = 0; i < ne; i++) {
		int v0 = edges[i][0];
		int v1 = edges[i][1];
		int w = edges[i][2];
		graph[v0][v1] = w;
		if (v0 == start) {
			dist[v1] = w;
			parent[v1] = v0;
		}
	}

	int *dist = dijkstra(start,nv);
	for (int i = 0; i < nv; i++) {
		cout << "start = "<<start << " end =" << i << " dist = "<< dist[i] << " parent = " << parent[i] << endl;
	} 
	return 0;
} 

/*
memset初始化二维矩阵
1取最后一个字节 2->16->10
00000001 -> 0x01010101 -> 16843009
0
00000000 -> 00000000
-1
11111111 ->  
https://blog.csdn.net/qq_53269459/article/details/119535151

dijkstra算法参考：https://baike.baidu.com/item/%E8%BF%AA%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95/23665989 
*/

在这里插入图片描述

弗洛伊德算法

求所有点之间的最短路径

#include<iostream>
#include<vector>
#include<string.h>
#define N 10
#define INF 65535
using namespace std;

int graph[N][N];

/*
弗洛伊德算法
	求所有点之间的最短距离 
核心思想：
	经由中转点k所能得到的最短距离
	弗洛伊德是一种动态规划算法,u是起点，v是终点，k是中转点 
	for k
		for u
			for v
				dist[u][v] = min(dist[u][v],dist[u][k]+dist[k][v])
	时间复杂度O(n^3) 
问题：
	为什么是最外层为中转点k 
	因为floyd本质目的是对于每个点对i-j的距离可以被其它点优化，而且可以被多个点共同优化，
	如果循环k在内层，那么i,j每次只能得到一个点的优化。
	例如 
	1 -> 3 -> 4 ->2
	\ _ _ _ _ _ /
	点1-2的路径只能通过单一的点，k在最内部： 
	1与2之间的最短路径，要么通过3，要么通过4； 1->3->2, 和1->4->2; 没有考虑到同时使用3，4来优化,即1->3->4->2
参考：https://blog.csdn.net/RunningBeef/article/details/114683747 
*/ 

void floyed(int n) {
	//中间点 
	for (int k = 0; k < n; k++) {
		//起点 
		for (int v0 = 0; v0 < n; v0++) {
			//终点
			for (int v1 = 0; v1 < n; v1++) {
				if (graph[v0][k] + graph[k][v1] < graph[v0][v1]) {
					graph[v0][v1] = graph[v0][k] + graph[k][v1];
				} 
			} 
		} 
	}
}

int main() {
	int ne = 10, nv = 6;
	int edges[][3] = {{0,1,2},{0,2,5},{1,2,1},{1,3,3},{2,3,3},{2,4,4},{2,5,1},{3,4,1},{3,5,4},{4,5,1}};
	
	//二维整型数组直接利用 memset() 函数初始化时，只能初始化为 0 或 -1 ，否则将会被设为随机值
	//手动初始化 
	for (int i = 0; i < nv; i++) {
		for (int j = 0; j < nv; j++) {
			graph[i][j] = INF;
		}
		graph[i][i] = 0;
	}
	//初始化边 
	int start = 1;
	for (int i = 0; i < ne; i++) {
		int v0 = edges[i][0];
		int v1 = edges[i][1];
		int w = edges[i][2];
		graph[v0][v1] = w;
	}

	floyed(nv);
	for (int i = 0; i < nv; i++) {
		for (int j = 0; j < nv; j++) {
			cout << graph[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

在这里插入图片描述

BFS

广度优先遍历求两个点之间的最短路径
当遍历到目标节点，停止遍历，BFS求的是start到end之间的直线距离

  1 -5
 /  \  \
0     3-4
 \ 2 /

求0,4的最短路径

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef vector<vector<int>> VVI; 
typedef vector<int> VI;
#define rep(i,n) for(int i = 0, i < n; i++)

VI bfs(VVI &edges,int n, int org, int dst) {
	//建图 
	VVI g(n);
	for (VI e : edges) {
		int start = e[0], end = e[1];
		g[start].push_back(end);
		g[end].push_back(start); 
	}
	//初始化距离和父节点数组 
	VI dis(n,-1);
	VI fa(n,-1);
	//初始化队列 
	queue<int> q;
	q.push(org);
	dis[org] = 0; 
	fa[org] = -1;
	//bfs求解最短路径 
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int y : g[x]) {
			if (y == dst) {
				fa[y] = x;
				dis[dst] = dis[x] + 1;
				break;
			}
			if (dis[y] < 0) {
				fa[y] = x;
				dis[y] = dis[x] + 1;
				q.push(y);
			}
		}
		if (dis[dst] != -1) {
			break;
		}
	}
	cout << dis[dst] << endl;
	VI path;
	int x = dst;
	while(x != -1) {
		path.push_back(x);
		x = fa[x];
	}
	reverse(path.begin(),path.end());
	return path;
}

int main() {
	VVI edges = {{0,1},{0,2},{0,3},{1,3},{1,5},{2,3},{3,4},{5,4}};
	int n = 6;
	VI path = bfs(edges,n,0,4);
	for (int i = 0, n = path.size(); i < n; i++) {
		cout << path[i] << (i==n-1 ? "" : " -> ");
	}
	cout << endl;
}