2023.11.15 每日一题（AI自生成应用）【C++】【Python】【Java】【Go】 动态路径分析

目录

一、题目

二、解决方法

三、改进

一、题目

背景： 在一个城市中，有数个交通节点，每个节点间有双向道路相连。每条道路具有一个初始权重，代表通行该路段的成本（例如时间、费用等）。随着时间的变化，道路的权重可能会发生变化，比如由于交通堵塞或道路维修。

问题： 设计一个算法，以处理以下两种类型的查询：

  1. 更新查询：给定两个节点及新的权重值，更新这两个节点之间道路的权重。
  2. 最短路径查询：给定两个节点，找出这两个节点之间的最短路径及其权重。

输入格式：

输出格式：

  • 对于每个最短路径查询，输出一个整数，表示最短路径的权重。如果两个节点之间没有路径，则输出 -1。

实际应用： 这个问题可以应用于交通管理系统，例如实时更新交通状况并为司机提供最优路线。也适用于网络数据流量管理，其中节点代表数据中心，道路代表连接它们的网络。

挑战：

  • 设计一个高效的数据结构来存储和更新节点间的道路权重。
  • 实现一个算法来快速回答最短路径查询，考虑到道路权重可能频繁变化。

二、解决方法

解决：

为了解决这个动态路径分析问题，我们可以采用以下策略：

  1. 数据结构：使用邻接表来表示图，其中每个节点都有一个列表存储它与其他节点的连接及其权重。
  2. 路径更新：对于更新操作，我们只需要修改邻接表中对应的权重。
  3. 最短路径查询：使用 Dijkstra 算法来找到最短路径。由于权重可能会频繁变化，我们在每次查询时都从头开始执行 Dijkstra 算法。

C++实现：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

typedef pair<int, int> pii; // pair of (weight, node)

class Graph {
    int V; // Number of vertices
    vector<vector<pii>> adj; // Adjacency list

public:
    Graph(int V) : V(V), adj(V) {}

    void addEdge(int u, int v, int w) {
        adj[u].push_back({w, v});
        adj[v].push_back({w, u}); // For undirected graph
    }

    void updateEdge(int u, int v, int w) {
        // Update weight for edge u-v
        for (auto &p : adj[u]) {
            if (p.second == v) {
                p.first = w;
                break;
            }
        }
        for (auto &p : adj[v]) {
            if (p.second == u) {
                p.first = w;
                break;
            }
        }
    }

    int shortestPath(int source, int destination) {
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        vector<int> dist(V, INT_MAX);

        pq.push({0, source});
        dist[source] = 0;

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            for (auto &[w, v] : adj[u]) {
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }

        return (dist[destination] == INT_MAX) ? -1 : dist[destination];
    }
};

int main() {
    int N, M, u, v, w;
    cin >> N >> M;

    Graph g(N);

    for (int i = 0; i < M; ++i) {
        cin >> u >> v >> w;
        g.addEdge(u, v, w);
    }

    // Queries
    char queryType;
    while (cin >> queryType) {
        if (queryType == 'U') {
            cin >> u >> v >> w;
            g.updateEdge(u, v, w);
        } else if (queryType == 'Q') {
            cin >> u >> v;
            cout << g.shortestPath(u, v) << endl;
        }
    }

    return 0;
}

Python：

import heapq

class Graph:
    def __init__(self, V):
        self.V = V
        self.graph = {i: {} for i in range(V)}

    def add_edge(self, u, v, w):
        self.graph[u][v] = w
        self.graph[v][u] = w

    def update_edge(self, u, v, w):
        if v in self.graph[u]:
            self.graph[u][v] = w
        if u in self.graph[v]:
            self.graph[v][u] = w

    def shortest_path(self, source, destination):
        dist = [float('inf')] * self.V
        dist[source] = 0
        pq = [(0, source)]

        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue

            for v, w in self.graph[u].items():
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(pq, (dist[v], v))

        return dist[destination] if dist[destination] != float('inf') else -1

# Example usage
g = Graph(N)  # N is the number of vertices
# Add edges and handle queries similarly to the C++ example

JAVA：

import java.util.*;

public class Graph {
    private int V;
    private Map<Integer, Map<Integer, Integer>> adj;

    public Graph(int V) {
        this.V = V;
        this.adj = new HashMap<>();
        for (int i = 0; i < V; i++) {
            adj.put(i, new HashMap<>());
        }
    }

    public void addEdge(int u, int v, int w) {
        adj.get(u).put(v, w);
        adj.get(v).put(u, w);
    }

    public void updateEdge(int u, int v, int w) {
        if (adj.get(u).containsKey(v)) {
            adj.get(u).put(v, w);
        }
        if (adj.get(v).containsKey(u)) {
            adj.get(v).put(u, w);
        }
    }

    public int shortestPath(int source, int destination) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.add(new int[]{source, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];

            if (u == destination) {
                break;
            }

            for (Map.Entry<Integer, Integer> entry : adj.get(u).entrySet()) {
                int v = entry.getKey();
                int weight = entry.getValue();

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new int[]{v, dist[v]});
                }
            }
        }

        return dist[destination] == Integer.MAX_VALUE ? -1 : dist[destination];
    }

    // Example usage
    public static void main(String[] args) {
        Graph g = new Graph(N); // N is the number of vertices
        // Add edges and handle queries similarly to the C++ example
    }
}

Go语言：

package main

import (
	"container/heap"
	"fmt"
	"math"
)

type Edge struct {
	node, weight int
}

type Graph struct {
	V     int
	edges map[int]map[int]int
}

func NewGraph(V int) *Graph {
	g := &Graph{
		V:     V,
		edges: make(map[int]map[int]int),
	}
	for i := 0; i < V; i++ {
		g.edges[i] = make(map[int]int)
	}
	return g
}
func (g *Graph) UpdateEdge(u, v, w int) {
	if _, ok := g.edges[u][v]; ok {
		g.edges[u][v] = w
	}
	if _, ok := g.edges[v][u]; ok {
		g.edges[v][u] = w
	}
}

func (g *Graph) ShortestPath(source, destination int) int {
	dist := make([]int, g.V)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[source] = 0

	pq := make(PriorityQueue, 0)
	heap.Init(&pq)
	heap.Push(&pq, &Item{
		value:    source,
		priority: 0,
	})

	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		u := item.value

		if u == destination {
			break
		}

		for v, w := range g.edges[u] {
			if dist[u]+w < dist[v] {
				dist[v] = dist[u] + w
				heap.Push(&pq, &Item{
					value:    v,
					priority: dist[v],
				})
			}
		}
	}

	if dist[destination] == math.MaxInt32 {
		return -1
	}
	return dist[destination]
}

// Define the priority queue used for Dijkstra's algorithm
type Item struct {
	value    int // The node index
	priority int // The node's priority (distance)
	index    int // The index of the item in the heap
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil
	item.index = -1
	*pq = old[0 : n-1]
	return item
}

func main() {
	// Example usage
	g := NewGraph(N) // N is the number of vertices
	// Add edges and handle queries similarly to the C++ example
}

三、改进

  1. 效率问题：每次查询最短路径时都需要从头执行 Dijkstra 算法。在频繁更新边权重的场景中，这可能导致效率低下。
  2. 数据结构选择：现有实现使用邻接表来存储图，这对于稀疏图是合适的。但对于密集图，这种表示方式可能导致内存使用不经济。

改进：

  1. 增量更新算法：对于频繁更新的场景，可以考虑使用更高级的图算法，如“动态最短路径算法”。这类算法可以在不重新计算整个图的情况下，有效更新最短路径。
  2. 数据结构优化：针对不同类型的图（稀疏或密集），选择合适的数据结构。例如，对于密集图，可以使用邻接矩阵来代替邻接表。
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int MAX_V = 1000; // 假设图中最多有1000个节点

class Graph {
    int V; // 顶点数
    vector<vector<int>> adjMatrix; // 邻接矩阵

public:
    Graph(int V) : V(V), adjMatrix(V, vector<int>(V, INT_MAX)) {}

    void addEdge(int u, int v, int w) {
        adjMatrix[u][v] = w;
        adjMatrix[v][u] = w;
    }

    void updateEdge(int u, int v, int w) {
        adjMatrix[u][v] = w;
        adjMatrix[v][u] = w;
    }

    int shortestPath(int source, int destination) {
        vector<int> dist(V, INT_MAX);
        vector<bool> sptSet(V, false);

        dist[source] = 0;

        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, sptSet);
            sptSet[u] = true;

            for (int v = 0; v < V; v++) {
                if (!sptSet[v] && adjMatrix[u][v] != INT_MAX && dist[u] != INT_MAX &&
                    dist[u] + adjMatrix[u][v] < dist[v]) {
                    dist[v] = dist[u] + adjMatrix[u][v];
                }
            }
        }

        return (dist[destination] == INT_MAX) ? -1 : dist[destination];
    }

private:
    int minDistance(const vector<int> &dist, const vector<bool> &sptSet) {
        int min = INT_MAX, min_index;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
        }

        return min_index;
    }
};

int main() {
    // 示例用法
    int N, M, u, v, w;
    cin >> N >> M;

    Graph g(N);

    for (int i = 0; i < M; ++i) {
        cin >> u >> v >> w;
        g.addEdge(u, v, w);
    }

    // 处理查询
    // ...
}

        这个实现针对密集图进行了优化，但它不包括动态最短路径算法的实现。动态最短路径算法通常更复杂，可能需要使用更高级的数据结构和算法技巧。这种算法的实现和优化通常是图算法研究的前沿话题。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/150586.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

PPT转PDF转换器：便捷的批量PPT转PDF转换软件

PPT转PDF转换器：便捷的批量PPT转PDF转换软件

在数字化时代&#xff0c;文档转换已成为日常工作不可或缺的一环。特别是对于那些需要转发或发布演示文稿的人来说&#xff0c;如果希望共享给他人的PPT文件在演示过程中不被修改&#xff0c;那么将PPT文件转换为PDF格式已经成为一个常见的选择。大多数PDF阅读器程序都支持全屏…
阅读更多...
debian 修改镜像源为阿里云【详细步骤】

debian 修改镜像源为阿里云【详细步骤】

文章目录 修改步骤第 1 步：安装 vim 软件第 2 步：备份源第 3 步：修改为阿里云镜像参考👉 背景：在 Docker 中安装了 jenkins 容器。查看系统，发现是 debian 11（bullseye）。 👉 目标：修改 debian bullseye 的镜像为阿里云镜像，加速软件安装。 修改步骤 第 1 步：…
阅读更多...
深度学习+python+opencv实现动物识别 - 图像识别 计算机竞赛

深度学习+python+opencv实现动物识别 - 图像识别 计算机竞赛

文章目录 0 前言1 课题背景2 实现效果3 卷积神经网络3.1卷积层3.2 池化层3.3 激活函数&#xff1a;3.4 全连接层3.5 使用tensorflow中keras模块实现卷积神经网络 4 inception_v3网络5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; *…
阅读更多...
Synchronized面试题

Synchronized面试题

一&#xff1a;轻量锁和偏向锁的区别&#xff1a; &#xff08;1&#xff09;争夺轻量锁失败时&#xff0c;自旋尝试抢占锁 &#xff08;2&#xff09;轻量级锁每次退出同步块都需要释放锁&#xff0c;而偏向锁是在竞争发生时才释放锁&#xff0c;线程不会主动释放偏向锁 二&…
阅读更多...
浅尝：iOS的CoreGraphics和Flutter的Canvas

浅尝：iOS的CoreGraphics和Flutter的Canvas

iOS的CoreGraphic 基本就是创建一个自定义的UIView&#xff0c;然后重写drawRect方法&#xff0c;在此方法里使用UIGraphicsGetCurrentContext()来绘制目标图形和样式 #import <UIKit/UIKit.h>interface MyGraphicView : UIView endimplementation MyGraphicView// Onl…
阅读更多...
酷开系统 酷开科技，将家庭娱乐推向新高潮

酷开系统 酷开科技，将家庭娱乐推向新高潮

在当今数字化时代&#xff0c;家庭娱乐已经成为人们日常生活中不可或缺的一部分。如果你厌倦了传统的家庭娱乐方式&#xff0c;想要一种全新的、充满惊喜的娱乐体验&#xff0c;那么&#xff0c;不妨进入到酷开科技的世界&#xff0c;作为智能电视行业领军企业&#xff0c;酷开…
阅读更多...
理解 R-CNN：目标检测的一场革命

理解 R-CNN：目标检测的一场革命

一、介绍 对象检测是一项基本的计算机视觉任务&#xff0c;涉及定位和识别图像或视频中的对象。多年来&#xff0c;人们开发了多种方法来应对这一挑战&#xff0c;但基于区域的卷积神经网络&#xff08;R-CNN&#xff09;的发展标志着目标检测领域的重大突破。R-CNN 及其后续变…
阅读更多...
深度学习之基于Pytorch和OCR的识别文本检测系统

深度学习之基于Pytorch和OCR的识别文本检测系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介深度学习与OCRPyTorch在OCR中的应用文本检测系统的关键组成部分1. 图像预处理2. 深度学习模型3. 文本检测算法4. 后处理 二、功能三、系统四. 总结 一项目简…
阅读更多...
后端接口性能优化分析-问题发现问题定义

后端接口性能优化分析-问题发现问题定义

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱吃芝士的土豆倪&#xff0c;24届校招生Java选手&#xff0c;很高兴认识大家&#x1f4d5;系列专栏&#xff1a;Spring源码、JUC源码&#x1f525;如果感觉博主的文章还不错的话&#xff0c;请&#x1f44d;三连支持&…
阅读更多...
图解系列--密码

图解系列--密码

1.概念 _1.对称密码与公钥密码 对称密码是指在加密和解密时使用同一密钥的方式。 公钥密码则是指在加密和解密时使用不同密钥的方式。因此&#xff0c;公钥密码又称为非对称密码。 _2.混合密码系统 对称密码和公钥密码结合起来的密码方式 _3.散列值 散列值就是用单向散列函数计…
阅读更多...
CSDN每日一题学习训练——Java版（二叉搜索树迭代器、二叉树中的最大路径和、按要求补齐数组）

CSDN每日一题学习训练——Java版（二叉搜索树迭代器、二叉树中的最大路径和、按要求补齐数组）

版本说明 当前版本号[20231115]。 版本修改说明20231115初版 目录 文章目录 版本说明目录二叉搜索树迭代器题目解题思路代码思路参考代码 二叉树中的最大路径和题目解题思路代码思路参考代码 按要求补齐数组题目解题思路代码思路参考代码 二叉搜索树迭代器 题目 实现一个二…
阅读更多...
UE4动作游戏实例RPG Action解析三：实现效果，三连击Combo，射线检测，显示血条，火球术

UE4动作游戏实例RPG Action解析三：实现效果，三连击Combo，射线检测，显示血条，火球术

一、三连Combo 实现武器三连击，要求： 1.下一段Combo可以随机选择， 2.在一定的时机才能再次检测输入 3. 等当前片段播放完才播放下一片段 1.1、蒙太奇设置 通过右键-新建蒙太奇片段，在蒙太奇里创建三个片段，并且移除相关连接，这样默认只会播放第一个片段 不同片段播…
阅读更多...
requests 2.13.0 版本的 https 连接慢漏提示

requests 2.13.0 版本的 https 连接慢漏提示

# 解决方案 requests 2.13.0 版本的 https 连接慢漏问题 问题背景&#xff1a;在使用requests 2.13.0版本时&#xff0c;发现存在一个缓慢的泄漏问题。这个问题只在使用https连接时出现。经过调查&#xff0c;发现这个问题与pyOpenSSL的使用有关。在使用pyOpenSSL与requests 2.…
阅读更多...
Ps：利用 AI 技术创建人像皮肤图层蒙版

Ps：利用 AI 技术创建人像皮肤图层蒙版

Photoshop 并没有提供专门选择人像皮肤的工具或命令&#xff08;色彩范围中的肤色选择非常不精准&#xff09;&#xff0c;但较新版的 Camera Raw 滤镜则提供了基于 AI 技术的选择人物并创建面部和身体皮肤蒙版的功能。 如果能将 Camera Raw 滤镜中创建的 AI 皮肤蒙版转换成 Ps…
阅读更多...
Qt图形视图框架：QGraphicsItem详解

Qt图形视图框架：QGraphicsItem详解

Qt图形视图框架&#xff1a;QGraphicsItem详解 Chapter1 Qt图形视图框架&#xff1a;QGraphicsItem详解Chapter2 自定义QGraphicsItem实现平移、改变尺寸和旋转1. 平移2. 改变尺寸3. 旋转完整代码如下&#xff1a;头文件源文件 Chapter1 Qt图形视图框架&#xff1a;QGraphicsIt…
阅读更多...
初试 jmeter做压力测试

初试 jmeter做压力测试

一.前言 压力测试是每一个Web应用程序上线之前都需要做的一个测试&#xff0c;他可以帮助我们发现系统中的瓶颈问题&#xff0c;减少发布到生产环境后出问题的几率&#xff1b;预估系统的承载能力&#xff0c;使我们能根据其做出一些应对措施。所以压力测试是一个非常重要的步…
阅读更多...
nodejs+vue黄河风景线旅游网站的设计与实现-微信小程序-安卓-python-PHP-计算机毕业设计

nodejs+vue黄河风景线旅游网站的设计与实现-微信小程序-安卓-python-PHP-计算机毕业设计

本文首先对该系统进行了详细地描述&#xff0c;然后对该系统进行了详细的描述。管理人员增加了系统首页、个人中心、用户管理、景点分类管理、景点简介管理、旅游路线管理、文章分类管理、公告文章管理、系统管理理等功能。这套黄河风景线旅游网站是根据当前的现实需要&#xf…
阅读更多...
接口

接口

文章目录 概述语法使用特性接口的继承抽象类和接口的区别 概述 电脑的USB口上&#xff0c;可以插&#xff1a;U盘、鼠标、键盘…所有符合USB协议的设备 电源插座插孔上&#xff0c;可以插&#xff1a;电脑、电视机、电饭煲…所有符合规范的设备 通过上述例子可以看出&#xff…
阅读更多...
.NET 7 创建Android项目 (拥有原生的界面设计能力，比MAUI更好的性能)

.NET 7 创建Android项目 (拥有原生的界面设计能力，比MAUI更好的性能)

vs2022默认移动开发使用的是maui项目模板&#xff0c;maui确实有很多亮点&#xff0c;就是对比android原生项目性能还需要优化&#xff0c;特别是启动app时无法达到秒开。后来发现vs2022中依然可以直接创建android项目&#xff0c;性能和原生Android基本一致。 1、搜索模板 dot…
阅读更多...
OPPO Watch纯手机开启远程ADB调试

OPPO Watch纯手机开启远程ADB调试

Wear OS手表中&#xff0c;我们可以直接在开发者设置中打开WiFi调试。但是这在OPPO等魔改Android系统中不再奏效。 需要什么&#xff1f;&#xff1f; 手表一台手机一个OTG转接头一个手表充电器一个 演示设备 手机&#xff1a; OPPO Find X手表&#xff1a; OPPO Watch 1代 …
阅读更多...
最新文章

Copyright @ 2022~2023