尽快，求解以下问题如图中第五题的程序要求，文件夹压缩包的形式发我，最好于4月30号中午12点前发我

求解最短路径
提供算法思想描述，程序结构，测试结果

设有n(n> 10)个城市之间的交通图。假设任意两个城市之间不一定有直接交通线路，权表示乘车时间。要求事先将交通图信息将存人磁盘文件中，求从某城市出发到其他城市的最少乘车时间和乘车路线。要求将结果以图形方式在屏幕上输出。

你这个问题就是一个加权无向图的最小路径求解的问题，我给个例子你参考一下，直接用现成的算法实现的，代码并不复杂，看看是否符合你的要求：

import matplotlib.pyplot as plt
import networkx

G2 = networkx.Graph()  # 创建：空的 无向图
#创建加权边，a、b、c等代表城市，后边的值代表乘车时间
edges = [("a", "b", 5), ("a", "c",13), ("a", "e",10),("a", "g", 6), 
        ("a", "i", 5),("a", "k", 6),("a", "l", 2), ("a", "m", 5),
        ("b", "c", 3), ("b", "i", 1),("c", "d", 9), ("d", "e",11),
        ("e", "f", 9), ("f", "g", 6),("g", "h", 7), ("h", "i", 4),
        ("i", "j", 9), ("j", "k", 6),("k", "l", 7), ("l", "m", 4)]
G2.add_weighted_edges_from(edges)  # 向图中添加多条赋权边: (node1,node2,weight)
#指定要求解的两个点
source = 'b'
target = 'f'
# 两个指定顶点之间的最短加权路径
minWPath= networkx.dijkstra_path(G2, source=source, target=target)
print(f"顶点 {source} 到 顶点 {target} 的最短加权路径: {minWPath}")
# 两个指定顶点之间的最短加权路径的长度
lMinWPath = networkx.dijkstra_path_length(G2, source=source, target=target)  #最短加权路径长度
print(f"顶点 {source} 到 顶点 {target} 的最短加权路径长度: {lMinWPath}")

pos = networkx.spring_layout(G2)  # 用 FR算法排列节点
networkx.draw(G2, pos, with_labels=True, alpha=0.5) #画所有节点
labels = networkx.get_edge_attributes(G2,'weight') #取加权值为标签
networkx.draw_networkx_edge_labels(G2, pos, edge_labels = labels) #画边和标签
posCopy = pos.copy()  #复制所有节点
edgesCopy = [] #最小路径加权边
#遍历所有节点，保留最小路径相关节点
for k in pos.keys():
    if k not in minWPath:
        posCopy.pop(k)
#遍历所有加权边，取出最小路径相关加权边
for i in range(len(minWPath)-1):
    for edge in edges:
        if minWPath[i] in edge and  minWPath[i+1] in edge:
            edgesCopy.append(edge)
            break
minG2 = networkx.Graph() #创建空无向图
minG2.add_weighted_edges_from(edgesCopy) #向图中添加最小路径加权边
networkx.draw(minG2, posCopy, with_labels=False, alpha=1, edge_color='red')  #用红色标记最小路径边
plt.show()

算法思想描述：tsp

程序结构：
之前写的

 #include<iostream>
#include<math.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std; 
int main()
{
    int i,j,k,min,brief,n;
    int D[20][20];
    cout<<"城市个数：";
    cin>>n;
    int b=(int)pow(2,n-1);
      for(i=0;i<n;i++)
        for(j=0;j<n;j++)
              cin>>D[i][j];
    cout<<"输入起始城市点：";
    
    int begin;
    cin>> begin;
    cout<<"起点为"<<begin<<"的城市路线新图："<<endl; 
    for(int i=0;i<n;i++){ 
    if(D[0][i]!=0&&D[begin-1][i]!=0&&D[i][0]!=0&&D[i][begin-1]!=0){
        int t=D[0][i];
    D[0][i]=D[begin-1][i];
    D[begin-1][i]=t;
     t=D[i][0];
    D[i][0]=D[i][begin-1];
    D[i][begin-1]=t;
        
    }else continue;
    
    } 
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
              cout<<D[i][j]<<" ";
    cout<<endl;
    }
        
      int ** Route = (int **)calloc(n, sizeof(int *));
      int ** Mat = (int **)calloc(n, sizeof(int *));
      for(i=0;i<n;i++)
      {
        Route[i] = (int *)calloc(b*b, sizeof(int))+i*b;
        Mat[i] = (int *)calloc(b*b, sizeof(int))+i*b;
      }
      for(i=0;i<b;i++)
           for(j=0;j<n;j++)
        {
            Route[j][i] = -1;
               Mat[j][i] = -1;
        }
      for(i=0;i<n;i++)//初始化第0列 
        Route[i][0] = D[i][0];    
      for(i=1;i<b-1;i++)
        for(j=1;j<n;j++)//依次进行第i次迭代 
            if( ((int)pow(2,j-1) & i) == 0)//子集V[j不包含i 
            {
                min=999;
                for(k=1;k<n;k++)
                if( (int)pow(2,k-1) & i )
                {
                    brief = D[j][k] + Route[k][i-(int)pow(2,k-1)]; 
                    if(brief < min)
                    {
                        min = brief;
                        Route[j][i] = min;
                        Mat[j][i] = k;//局部最优决策
                    }
                }    
            }
    min=999;
      for(k=1;k<n;k++)
    {
        brief = D[0][k] + Route[k][b-1 - (int)pow(2,k-1)];
        if(brief < min)
        {
            min = brief;
            Route[0][b-1] = min;//最优解
            Mat[0][b-1] = k;
        }
    }
    cout<<"最短时间："<<Route[0][b-1]<<endl;//最短路径长度
    cout<<"最短路径："<<begin;
    for(i=b-1,j=0; i>0; )
    {
        j = Mat[j][i];
        i = i - (int)pow(2,j-1);
        if(j!=begin-1)
        cout<<"->"<<j+1;
        else cout<<"->"<<"1";
    }
    cout<<"->"<<begin<<endl;
    cout<<"城市最短通勤时间结果："<<endl;
    for(i=0;i<n;i++)
    {
        for(j=0;j<b;j++)
              printf("%d\t",Route[i][j]);
        cout<<endl;
    }
    free(Route);
    free(Mat);
    return 0;
}

测试结果：

要求事先将交通图信息将存人磁盘文件中：
你自己可以写一下，读文件到二维数组，不行也可以联系，改一下简单，这是之前做数据结构与算法的老代码了

必须帮帮你
【【图论】【最短路】城市问题】https://mbd.baidu.com/ma/s/eBV4lT0U