首页 > 电脑常识 > 区块链

算法实验3-1

admin 区块链 2021-05-25 09:26:47 贪心算法 
后台-系统设置-扩展变量-手机广告位-内容正文底部

贪心策略,单源最短路径

#include<bits/stdc++.h>
using namespace std;
int number[100][100] = {0};
int dis[100] = {0};
int book[100] = {0};

struct x{
    vector<int> path;
}Path[100];

const int INF = 0x3f3f3f3f;
int main()
{
    int n, c;
    cout << "请输入节点个数和起始点 :  \n";
    cin >> n >> c;
    cout << "请输入距离矩阵:\n";
    for (int i = 0; i < n; i++)
    {
       for (int j = 0; j < n; j++)
       {
           cin >> number[i][j];
       }
    }
    for (int i = 0; i < n; i++)
    {
        dis[i] = number[c - 1][i];
        Path[i].path.push_back(c);
    }
    book[c - 1] = 1;

    int min = 0 , s = 0;
    for (int i = 0; i < n-1; i++)
    {
         min = INF;

         for (int j = 0; j < n; j++)
         {
             if(dis[j] != -1 && dis[j] != 0 && book[j] == 0 && dis[j] < min)
             {
                 min = dis[j];
                 s = j;
             }
         }

         book[s] = 1;

         for (int i = 0; i < n; i++)
         {
            if(number[s][i] != -1)
            {
                if(dis[i] == -1)
                {
                    dis[i] = dis[s] + number[s][i];
                    Path[i].path = Path[s].path;
                    Path[i].path.push_back(i+1);
                }
                else
                if(dis[i] > dis[s] + number[s][i])
                {
                    dis[i] = dis[s] + number[s][i];
                    Path[i].path = Path[s].path;
                    Path[i].path.push_back(i+1);
                }
                else
                {
                    if(Path[i].path.back() != i + 1)
                    {
                        Path[i].path.push_back(i+1);
                    }
                }

            }
         }
    }
    for (int i = 0; i < n; i++)
    {
        cout << "从" << c  << "点出发"
             << "到" << i + 1 << "点的最短路径为:  ";
        for (int j = 0; j < Path[i].path.size();j++)
        {
            cout << Path[i].path[j]<<"  ";
        }
        cout << " 最短路径长度为:"<<dis[i];
        cout << endl;
    }

        system("pause");
}

在这里插入图片描述

文章来源:https://blog.csdn.net/caoxiaobao1207/article/details/117191628

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://www.jcdi.cn/qukuailian/30825.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码