图+dijkstra最短路
2023-08-20 14:51:54
发布于：河北
7阅读
0回复
0点赞
图：
图的概念：
完全图：
任意两个顶点之间都存在边
无向完全图：
图中任意两个点都存在边
有向完全图：
图中任意两个顶点都存在方向相反的边
稀疏图与稠密图：
稀疏图：
图中的边相对较少，边之间的链接相对稀疏
用链表（邻接表）解决
稠密图：
图中的边相对较多，边之间的连接相对密集
用二维数组（邻接矩阵）解决
路径：
指从一个顶点到另一个顶点的连续边构成的序列。
图的导入：
bool bfs()
{
queue<int> q;
vis[a] = 1;
q.push(a);
while(!q.empty())
{
int cp = q.front();
if(cp == b)
{
return true;
}
q.pop();
for(int i = 0;i < v[cp].size();i++)
{
int np = v[cp][i];
if(!vis[np])
{
vis[np] = 1;
q.push(np);
}
}
}
return false;
}
dijkstra最短路：
dijkstra最短路 迪杰斯特拉
dis[N]最短距离数组
伪代码：
void dijkstra()
{
//1.初始化
memset(dis,0x3f,sizeof dis);
dis[起点] = 0;
//2.循环
for(n-1次)
{
t = 没标记的 距离最小的
vis[t] = true;
for(next : t相接的点)
{
if(vis[next)
{
continue;
}
//3.松弛 relax 更新
if(dis[naxt)+w[t][next]<dis[next])
{
dis[naxt]=dis[t]+w[t][next];
}
}
}
}
有帮助，赞一个