图论中路径问题及其应用 公共管理专业

题 目 ： 图 论 中 最 短 路 问 题 及 其 应 用摘 要 ：图 论 作 为 数 学 中 重 要 的 一 个 分 支 ， 自 从1736年 被 大 科 学 家 欧 拉 提 出 后 就 一 直 是 数 学 界 研 究中 的 重 点 。 图 论 中 研 究 的 对 象 是 图 ， 图 是 事 件及 事 件 之 间 联 系 的 抽 象 。 人 们 总 是 希 望 更 加 高效 的 处 理 事 件 与 事 件 的 联 系 ， 因 此 衍 生 出 了 最短 路 问 题 。图论中最短路问题在生活中的应用及其广泛 ， 小 到 管 道 铺 设 ， 厂 区 铺 设 ， 大 到 城 市 中 交通 路 网 的 规 划 优 化 ， 都 离 不 开 优 化 的 思 想 。 最短路径问题有多种算法，其中Dijkstra 算法是最典 型 的 算 法 。 Ford 算 法 和 Floyd算 法 。 本 文 主 要 介绍Dijkstra 和Floyed 这两种算法的基本定义以及简介 。除 了 对 Dijkstra 和 Floyed 这 两 种 算 法 的 基 本 定 义及 算 法 进 行 简 单 介 绍 以 外 ， 本 文 还 将 引 用 经 典的 商 人 过 河 问 题 作 为 实 例 ， 来 具 体 阐 述 图 论 中最 短 路 问 题 以 及 其 在 实 际 中 的 应 用 。关键词：图论、最短路、最短路径规划 、 Dijkstra 算 法 、 Floyd算 法毕业设计（论文）外文摘要Title ： Shortest path problem in Graph Theory and its ApplicationAbstractGraph theory, as an important branch of mathematics, has been the focus of mathematical research since it was put forward by Euler, a great scientist, in 1736. Graph is the object of study in graph theory, and graph is the abstraction of the relation between event and event.People always want to deal with the relationship between events and events more efficiently, so the shortest path problem arises. The problem of shortest road in graph theory is widely used in daily life, from pipeline laying, factory area laying and planning optimization of traffic network to city, all of which can...