最短路径算法

亦凉 2022-07-11 14:09 260阅读 0赞

最短路径[算法][Link 1]

\#include <iostream>

void path()\{

//val\[i\]\[j\]从i点到j点的距离，如果不可到达到，设置成0

int val\[8\]\[8\];

//res\[i\]\[j\]从i点到j点的最短距离，我们只要得到res\[0\]\[7\]

int res\[8\]\[8\];

//fa\[i\]i点的前一个最短距离点

int fa\[8\];

for (int i = 0; i<8; i++) \{

for (int j = 0; j<8; j++)\{

val\[i\]\[j\] = 0;

res\[i\]\[j\] = 10000;

\}

fa\[i\] = -1;

\}

res\[0\]\[0\] = 0;

val\[0\]\[1\] = 13;

val\[0\]\[2\] = 15;

val\[0\]\[3\] = 16;

val\[1\]\[4\] = 18;

val\[1\]\[5\] = 17;

val\[1\]\[6\] = 16;

val\[2\]\[4\] = 18;

val\[2\]\[5\] = 20;

val\[2\]\[6\] = 30;

val\[3\]\[4\] = 11;

val\[3\]\[5\] = 9;

val\[3\]\[6\] = 13;

val\[4\]\[7\] = 16;

val\[5\]\[7\] = 14;

val\[6\]\[7\] = 17;

for (int i = 1; i<8; i++) \{

for (int j = 0; j<i; j++)\{

if (val\[j\]\[i\] != 0) \{

if (res\[0\]\[j\] +val\[j\]\[i\]<res\[0\]\[i\]) \{

res\[0\]\[i\] = res\[0\]\[j\] +val\[j\]\[i\];

fa\[i\] = j;

\}

\}

\}

\}

int point = 7;

std::cout << 7 << "";

while (fa\[point\] != -1) \{

std::cout << "<---" << fa\[point\];

point = fa\[point\];

\}

std::cout << std::endl;

std::cout << res\[0\]\[7\] <<std::endl;

\}

int main(int argc, const char \* argv\[\]) \{

// insert code here...

std::cout << "Hello,World!\\n";

path();

system("pause");

return 0;

\}

运行结果：

![Center][]

[Link 1]: http://lib.csdn.net/base/datastructure
[Center]: /images/20220711/a5c48249b568485dad0355637d004d2e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读

相关图：最短路径算法

为笔试题总是出这个，于是想写下思路首先这个算法能解决从起始点，到各个点的最短路径问题. 但是不能解决权值为负数的情况。并且时间复杂度为O(n^2),并且能用堆进行...

一时失言乱红尘/ 2024年04月17日 05:57/ 0 赞/ 56 阅读

相关最短路径算法

到底是贪心还是动态规划？ Dijkstra算法抽象问题，选择合适的数据结构抽象问题权重图，本质求两节点最小权重值从起点开始遍历所有的临接节点，将节点权重维护

亦凉/ 2023年06月23日 03:00/ 0 赞/ 163 阅读

相关最短路径Dijkstra算法

最短路径Dijkstra算法本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。本博文作为学习资料整理。附书的截图： ![Center]

素颜马尾好姑娘i/ 2022年08月21日 03:27/ 0 赞/ 261 阅读

相关最短路径解决算法

> 一.问题引入 > > 问题：从某顶点出发，沿图的边到达另一顶点（O(n2)Xn个，总体为3次方）所经过的路 > > 径中，各边上权值之和最小的一条路径—

蔚落/ 2022年08月20日 13:12/ 0 赞/ 245 阅读

相关最短路径算法

最短路径[算法][Link 1] \include <iostream> void path()\{ //val\[i\]\[j\]从i点到j点的距离，如果

亦凉/ 2022年07月11日 14:09/ 0 赞/ 261 阅读

相关最短路径（Dijkstra）算法

一、算法功能：给定一个出发点(单源点)和一个有向网`G=(V, E)`, 求出源点到其它各顶点之间的最短路径。 -------------------- 二、算法

Love The Way You Lie/ 2022年06月14日 01:50/ 0 赞/ 294 阅读

相关最短路径算法实现

什么是最短路径呢？考虑到带权路径图，我们把一条路径上经过的权值之和是该路径的路径长度或者是带权路径长度。那么我来个案例，比如我们还是村庄之间修路，我们指定了一个村庄起点和

妖狐艹你老母/ 2022年06月03日 02:58/ 0 赞/ 307 阅读

相关最短路径—Floyd算法

Floyd算法： 1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w

冷不防/ 2022年05月12日 05:50/ 0 赞/ 288 阅读

相关最短路径算法

1 include <iostream> 2 using namespace std; 3 4 const int INF = 1

古城微笑少年丶/ 2022年01月07日 12:53/ 0 赞/ 578 阅读

相关求最短路径算法

public static int findPath(int[][] rout, boolean[] visited, int start,

淡淡的烟草味﹌/ 2021年06月24日 15:57/ 0 赞/ 526 阅读