贪心算法之dijkstra(代码片段)

关键词：

贪心算法的主要思想就是通过不断求解局部最优解，最后求出最优解或者最优解的近似值，不能保证一定为最优解。

Dijistra算法，选取没有选择过的点到已经选择过得点组成的集合中最短的距离的点。然后更新已选择的点到没有选择的点的距离。

已经选择的点是一个整体。

具体算法如下：

#include <iostream>
#include <stack>

using namespace std;

const int IDF = 1e7; //距离最大值
const int N = 100; //点的数量最大值
int map[N][N]; //点与点之间的距离
int n; //点的数量
int m; //线的数量
int dist[N]; //源点到其他点的距离
bool flag[N]; //是否已加入找到集
int p[N]; //记录路径

void Dijkstr(int u); //计算距离

void findpath(int u);

int main() 
    int u, v, w; //起点 终点 权重
    cout << "请输入点的个数：";
    cin >> n;
    cout << "请输入线的数量：";
    cin >> m;
    //初始化
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            map[i][j] = IDF;
        
    
    cout << "请输入两点及两点之间的距离：" << endl;
    while (m > 0) 
        cin >> u >> v >> w;
        map[u][v] = min(w, map[u][v]);
        m--;
    
    cout << "请输入起点：";
    cin >> u;
    cout << "信息输入完毕，开始计算地杰斯特拉距离" << endl;
    Dijkstr(u);
    findpath(u);
    return 0;


void findpath(int u) 
     int temp;
     stack<int> s;
     cout<<"源点为："<<u<<endl;
     for(int i = 0; i < n; i++)
         temp = p[i];
         while(temp != -1)
             s.push(temp);
             temp = p[temp];
         
         cout<<u<<"到"<<i<<"的距离为："<<dist[i]<<";路径为:";
         while(!s.empty())
             cout<<s.top()<<"--";
             s.pop();
         
         cout<<i<<endl;
     


void Dijkstr(int u) 
    //初始化
    for (int i = 0; i < n; i++) 
        dist[i] = map[u][i];
        flag[i] = false;
        if(dist[i] == IDF)
            p[i] = -1;
        else
            p[i] = u;
    
    //初始化起点
    dist[u] = 0;
    flag[u] = true;
    for (int j = 0; j < n; j++) //找n次
        //从没有找到的点中找最近的
        int temp = IDF;
        int t = u;
        for (int i = 0; i < n; i++) 
            if (flag[i] == false && dist[i] < temp) 
                temp = dist[i];
                t = i;
            
        
        if (t == u)  //没有找到 原距离不变
            return;
        
        //更新距离 找到t点
        flag[t] = true;
        for (int i = 0; i < n; i++) 
            if (flag[i] == false && map[t][i] + dist[t] < dist[i]) 
                dist[i] = map[t][i] + dist[t];
                p[i] = t;
            
        
    

算法模板之dijkstra(代码片段)

Dijkstra是求单源最短路的一种算法，它不能够处理含有负权边的图。本质是递推，依次求出距离起点最近的点。C++板子#include<bits/stdc++.h>#definelllonglong/*题目链接:https://www.luogu.com.cn/problem/P3371*/usingnamespacestd;constintN=5e5+50;constinti... 查看详情

图论算法dijkstra算法(代码片段)

最短路算法（三）Dijkstra算法PS:因为这两天忙着写GTMDsagment_tree，所以博客可能是sag+图论混搭着来，另外sag的基本知识就懒得整理了……Part1：Dijkstra算法基本信息以下，我们用dis[n]表示1->n的最短路径长度，vis[n]表示n号节点有... 查看详情

最短路径算法之dijkstra算法(代码片段)

参考：《大话数据结构》 这是一个按照路径长度递增的次序产生最短路径的算法。它并不是一次求出源点到目标点的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得... 查看详情

最短路问题之dijkstra算法(代码片段)

...博客的基础上，这是另一种方法求最短路径的问题。　　Dijkstra（迪杰斯特拉）算法：找到最短距离已经确定的点，从它出发更新相邻顶点的最短距离。此后不再关心前面已经确定的“最短距离已经确定的点”。　　Dijkstra... 查看详情

最短路径(邻接矩阵)-dijkstra算法(代码片段)

  Dijkstra算法又叫作迪杰斯特拉算法，是利用"贪心法"(在对问题进行求解时，总是做出在当前看来最好的选择策略)设计算法的一个成功范例。    适用条件:带权无环和无负权值    举个栗子:      Dijkstra算法... 查看详情

寻路算法之a*算法详解(代码片段)

...的算法去实现，常用的寻路算法主要有宽度最优搜索[1]、Dijkstra算法、贪心算法、A*搜索算法、B*搜索算法[2]、导航网格算法、JPS算法[3] 查看详情

贪心算法之集合覆盖问题详解(代码片段)

贪心算法之集合覆盖问题详解说明贪心算法是指在对某一问题求解时，每一步都寻找最优解的一种思路集合覆盖问题指有多个电台，每个电台都可以覆盖一定的区域，求可以覆盖所有地区的最小电台数量使用贪心算法求得的解不... 查看详情

贪心算法之prim(代码片段)

Prim与Dijistra算法有异曲同工之妙，只不过Dijistra是求最短路径，每次添加到集合中的是到固定起始点的最短距离，而Prim是求最小生成树，是整个图所有权重的最小和，每次添加到集合中的是到整个集合最短距离的点。Prim算法具... 查看详情

贪心算法之找零问题(代码片段)

贪心算法找零问题找零问题：假设商店老板需要找零n元钱，钱币的面额有：100元、50元、20元、5元、1元，如何找零使得所需钱币的数量最少？#greedyalgorithmmoney=[100,50,20,5,1]defchange_money(x):change=[0,0,0,0,0]fori,minenumerate(money):change[i]=x//m... 查看详情

算法学习——贪心算法之币种统计(代码片段)

算法描述币种统计单位给每一位员工发工资（精确到元），为了保证不临时换零钱，使得每个员工取款的张数最少，在取工资前统计所有员工所需要的各种票面的张数（约定票种为100,50,20,10,5,2,1元），并验证币种统计是否正确算... 查看详情

力扣刷题之贪心算法（c++）(代码片段)

（学习参考书：LeetCode101）贪心算法贪心算法采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到是全局最优的。解题步骤：将问题分解为若干个子问题，寻找合适的贪心策略求解每一个... 查看详情

贪心算法之乘船问题(代码片段)

有n个人，第i个人的重量为w[i]，每艘船的最大载重量均为c，且最多只能乘两个人。用最少的船装载所有人。 思路：从最轻的开始考虑，让最轻的和最重的一条船，若超出重量则可判定最重的只能一人一条船 代码：#include... 查看详情

c++算法主题系列之贪心算法的贪心之术(代码片段)

1.前言贪心算法是一种常见算法。是以人性之念的算法，面对众多选择时，总是趋利而行。因贪心算法以眼前利益为先，故总能保证当前的选择是最好的，但无法时时保证最终的选择是最好的。当然，在局部利益最大化的同时，... 查看详情

图的最短路径-----------dijkstra算法详解（tjuoj2870_thekthcity）(代码片段)

...图的搜索大致有三种比较常用的算法：迪杰斯特拉算法（Dijkstra算法）弗洛伊德算法（Floyd算法）SPFA算法Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。 算法... 查看详情

算法小讲堂之最短路算法(floyd+bellman+spfa+dijkstra)(代码片段)

前言如果你对图论相关知识一点也没有，那么建议您先去了解这些知识：https://acmer.blog.csdn.net/article/details/122310835，然后就可以快乐的学习最短路算法啦视频中绘图软件：https://csacademy.com/app/graph_editor/配套讲解视... 查看详情

程序员必会十大算法之贪心算法(代码片段)

例题假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有的地区都可以接收到信号代码publicclassMainpublicstaticvoidmain(String[]args)/***1.首先创建总的广播台和电视台*///创建一... 查看详情

算法学习——贪心算法之删数字（求最小值）(代码片段)

...此算法较为方便，链表可以直接移出某个位置的元素使用贪心算法，每一步都要达到最优从最高位开始，若下一位比上一位要小，则将上一位的数字移出，结束之后再次从最高位开始这里需要注意，会有特例当输入从小到大的的... 查看详情

算法学习——贪心算法之可拆背包(代码片段)

...种物品以及他们对应的价值，都是由用户输入的我们使用贪心算法，每一步取最大效益的物品放入背包之中（及单位价值为最高的物品单位价值=pi/wi）由以上思路，我们可以定义一个二维数组来接收用户输入的数 查看详情