首页 > 其他分享 >Dijkstra邻接矩阵板子

Dijkstra邻接矩阵板子

时间:2024-03-26 15:22:50浏览次数:24  
标签:dist int 邻接矩阵 st ++ Dijkstra return 板子

const int N = 510;//节点个数
int n;
int g[N][N];//图
int dist[N];//距离
bool st[N];//判断点是否访问过
int dijkstra(int s)//s表示起点,求s到任意点的最短距离
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 0; j < n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        for (int j = 0; j < n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        st[t] = true;
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

  

标签:dist,int,邻接矩阵,st,++,Dijkstra,return,板子
From: https://www.cnblogs.com/wockcow/p/18096734

相关文章

  • Floyd&Dijkstra
    拓展,多条路径Floyd算法Floyd算法是一种求解“多源最短路”问题的算法在Floyd算法中,图一般用邻接矩阵存储,边权可正可负(但不允许负环),利用动态规划的思想,逐步求解出任意两点之间的最短距离我们需要准备的东西很少,只需要一个d数组:int[N][N][N],初始为无穷大,无穷大表示两点之间没......
  • 数学基础板子(没有推导过程)
    \({\color{Red}声明:由于作者是个蒟蒻,所以本博客只含结论,不含推导过程。如果有大佬想看推导过程可以看(这里是传送门)}\)oi-wiki,教练,HaneDaniko素数筛法求素数用于求1~n的素数线性筛点击查看代码intprime[maxn];//保存素数boolis_not_prime[maxn]={1,1};//0和1......
  • 马拉车板子
    #include<bits/stdc++.h>#defineintlonglongusingnamespacestd;std::vector<int>manacher(std::strings){std::stringt="#";for(autoc:s){t+=c;t+='#';}cout<<t<<......
  • 1.基于搜索的路径规划:BFS、DFS、Dijkstra、A*、JPS
    1.概览可以对比不同算法的小动画 PathFinding.js(qiao.github.io)工作空间规划机器人有不同的形状和大小碰撞检测需要了解机器人的几何形状,耗时且难度大 我们希望将机器人表示为点,只需要把工作空间转换为配置空间C-obstacle,将原始的空间膨胀,这是一次性的C-space......
  • 邻接矩阵详解
    邻接矩阵是图论中用于表示图(Graph)结构的一种重要数据结构,特别适用于表示顶点之间连接关系的图形。在计算机科学和数学领域,它被广泛应用来编码无向图和有向图的信息。对于一个具有n个顶点的图G=(V,E),邻接矩阵是一个n×n的矩阵A,其中的行和列分别对应着图中的每个顶点。矩......
  • 最优乘车+最小花费(Dijkstra写法)
    题目描述H 城是一个旅游胜地,每年都有成千上万的人前来观光。为方便游客,巴士公司在各个旅游景点及宾馆,饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发,依次途经若干个巴士站,最终到达终点巴士站。一名旅客最近到 H 城旅游,他很想去 S......
  • 图Graph及相关算法(Dijkstra,Kruskal)
    目录无向图有向图邻接矩阵邻接表图的bfs,dfs二部图(二分图)有向无环图(DAG)拓扑排序(TopologicalSort)AOV网迪杰斯特拉Dijkstra最小生成树克鲁斯卡尔:Kruskal普里姆:prim图是多对多关系,是顶点和边的二元组和。无向图1.依附关系:边(v1,v2)依附于顶点v1,v2。2.完全图:所有......
  • 机器人路径规划:基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(提供Python代码)
    迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻......
  • dijkstra算法详解
    今天给大家讲解\(dijkstra\)图论最短路算法在讲解\(dijkstra\)算法之前,先来给大家讲解一下图论中的松弛操作。松弛,即\(relaxtion\),是一种编程学术语。举例说明,例如我们可以从某个机场坐飞机达到若干个机场,然后从这些机场出发,我们又需做火车前往若干个城镇。现在假设我们手里......
  • 单调队列 维护区间最值(板子+两道练手)
    1.P1886滑动窗口/【模板】单调队列https://www.luogu.com.cn/problem/P1886板子题,传送门在上方//Problem://P1886滑动窗口/【模板】单调队列////Contest:Luogu//URL:https://www.luogu.com.cn/problem/P1886//MemoryLimit:500MB//TimeLimit:1......