，利用graph解决图论模型的典型最短路径问题

img


起点 终点 距离
A T 3.6
A C 2.4
T A 3.6
T L 3
T E 2.4
E T 2.4
E P 2.4
C A 2.4
C L 1.2
L T 3.6
L C 1.2
L N 2.4
N L 3
N Q 3
Q N 2.4
Q P 1.2
P Q 1.8
P E 1.2
P V 1.2
V P 1.8
V K 2
K V 3
K J 3
K R 2
J H 1.8
J K 1.8
J B 3
J X 3.6
H J 3
H B 4.2
B H 3.6
B J 3
B I 3.6
R K 2.4
R X 2.4
R F 3.6
X J 1.8
X R 1.8
X O 2.4
X I 2.4
I B 3
I X 2.4
I S 3.6
I M 3
S I 2.4
S Y 2.4
F R 3
F U 3
U F 1.2
U W 1.8
U G 4.2
W G 1.2
W U 1.2
G U 1.2
G W 1.8
G O 2.4
O X 2.4
O G 1.2
O M 2.4
Y S 2.4
Y D 2.4
D Y 3.6
D M 3
M D 3.6
M I 1.2
M O 1.8
E N 2.4
N E 3
O F 1.2
F O 1.4
D S 2.4
S D 2.4
F V 1.2
V F 2.4
P U 1.8
U P 2
E W 1.8
W E 2.2
这是点位图和相邻点的距离，怎么用graph求出最短路径，graph不行的话应该用什么解决？怎么解决？

  • 以下回答由chatgpt基于相关博客总结生成:

    由参考资料可知，使用CGraph类可以方便地实现graph，并使用DFS或BFS算法解决典型的最短路径问题。对于以下问题，只需将距离信息表格转化为一个对应的有向图，并对图执行BFS算法即可，具体步骤如下：

    1. 根据距离信息表格，创建一个新的CGraph对象。例如，该题中距离信息表格如下：

    |0|2|7|INF|INF| |INF|0|1|6|INF| |INF|INF|0|INF|5| |INF|INF|12|0|8| |INF|INF|INF|INF|0|

    则创建对象的代码如下：

    CGraph graph(5);

    1. 将距离信息表格中的距离值转换为图上的边权值：

    |0 | 2 | 7 |INF|INF| |INF| 0 | 1 | 6 |INF| |INF|INF| 0 |INF| 5 | |INF|INF|12 | 0 | 8 | |INF|INF|INF|INF| 0 |

    在CGraph对象中，边权值的保存方式为邻接矩阵，所以将表格中的距离值转换为边权值只需将INF对应为0，其余非INF值不变即可，转换后的表格如下：

    |0|2|7| 0| 0| |0|0|1| 6| 0| |0|0|0| 0| 5| |0|0|12|0| 8| |0|0| 0| 0| 0|

    将表格转换为CGraph对象的代码如下：

    for(int i = 0; i < 5; i++) { for(int j = 0; j < 5; j++) { if(distance[i][j] != 0) {//i j 不相连接 graph.InsertEdge(i,j);//添加边 graph.m_Data[i][j]=distance[i][j];//将表格中距离作为边权值 graph.m_Data[j][i]=distance[j][i];//无向图中对称 }

        }
}
    1. 使用BFS算法从源节点解决该最短路径问题。假设源节点为0，则通过调用BFSTraverse函数即可得到结果。BFSTraverse遍历图的过程中，记录每个节点到源节点的最短距离，直至访问到目标节点为止。

    完整代码如下：（假设修订完成可以运行）