图论算法

标签：cin   cto   使用   利用   ram   遍历   details   就是   i++   

\(Floyd\)算法

例题(一本通P1342)

\(O(n^3)\)

设状态\(f[k][i][j]\):从i到j通过前k个点中的若干个的最短路径和
对于第k个中转点 ：

走：\(f[k-1][i][k]+f[k-1][k][j]\)

不走：\(f[k-1][i][j]\)

显然，可以压缩到二维

#include 
using namespace std;
struct node
{
	int x,y;
} V[10010];
double adm[1010][1010];
double floyd[1010][1010];
int n,m;
int s,t;

int main()
{
	cin>>n;
	for(int i=1;i>V[i].x>>V[i].y;
	cin>>m;
	for(int i=0;i>a>>b;
		adm[a][b]=adm[b][a]=min(sqrt((V[a].x-V[b].x)*(V[a].x-V[b].x)+(V[a].y-V[b].y)*(V[a].y-V[b].y)),adm[a][b]);//松弛 
	}
	cin>>s>>t;
	for(int k=1;k

\(dijkstra\)算法(不适用负权图)

基本思想：

1. 将图上的初始点看作一个集合S，其它点看作另一个集合

2. 根据初始点，求出其它点到初始点的距离d[i] （若相邻，则d[i]为边权值；若不相邻，则d[i]为无限大）

3. 选取最小的d[i]（记为d[x]），并将此d[i]边对应的点（记为x）加入集合S

（实际上，加入集合的这个点的d[x]值就是它到初始点的最短距离）

4. 再根据x，更新跟 x 相邻点 y 的d[y]值：d[y] = min{ d[y], d[x] + 边权值w[x][y] }，因为可能把距离调小，所以这个更新操作叫做松弛操作。

（仔细想想，为啥只更新跟x相邻点的d[y]，而不是更新所有跟集合 s 相邻点的 d 值？ 因为第三步只更新并确定了x点到初始点的最短距离，集合内其它点是之前加入的，也经历过第 4 步，所以与 x 没有相邻的点的 d 值是已经更新过的了，不会受到影响）

5. 重复3，4两步，直到目标点也加入了集合，此时目标点所对应的d[i]即为最短路径长度。
原文链接

时间复杂度\(O(n^2)\)

#include 
using namespace std;
const long long int INF=(1>n>>m>>sta;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(edg,0x3f,sizeof(edg));
	for(int i=1;i>x>>y>>z;
		edg[x][y]=min(z,edg[x][y]);//有向图写法 
	}
	dis[sta]=0;
	for(int i=1;idis[j]))//找到最短的dis 
				k=j;
		}
		vis[k]=1;//加入集合(即打上标记 
		for(int j=1;j=0x3f3f3f3f/2)
			cout

堆优化版\(dijkstra\)

直接使用堆(优先队列)来找最短dis的点

同时使用邻接表(vector或链式前向星实现)降低空间消耗

单次时间复杂度\(O(nlogn)\)

#include 
using namespace std;
const long long int INF=(1,vector >,greater > > q;/*第一维距离，第二维编号*/
inline void add(int x,int y,int z)//建邻接表 
{
	ver[++tot]=y;
	edge[tot]=z;
	nxt[tot]=head[x];//下一节点 
	head[x]=tot;
}
int main()
{
	cin>>n>>m>>sta;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	for(int i=1;i>x>>y>>z;
		add(x,y,z);
	}
	dis[sta]=0;
	q.push(make_pair(0,sta));//首元素入队列 
	while(!q.empty())
	{
		int x=q.top().second;//利用优先队列（堆）直接找到最短dis的点 
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;//加入集合 
		for(int i=head[x];i;i=nxt[i])//链表遍历 
		{
			int y=ver[i],z=edge[i];
			if(dis[y]>dis[x]+z)
			{
				dis[y]=dis[x]+z;
				q.push(make_pair(dis[y],y));//更新元素入队 
			}
		}
	}
	for(int i=1;i

未完待续......

------------------------------------------------------------------------------少女祈祷中......

图论算法

标签：cin   cto   使用   利用   ram   遍历   details   就是   i++   

原文地址：https://www.cnblogs.com/IzayoiMiku/p/12928228.html