多段图的最短路径问题

代码:

#include<bits/stdc++.h>
using namespace std;
int arc[20][20];
const int MAX = 1000;    // 假定边上的权值均不超过1000
int CreateGraph()
{
    int i,j,k;
    int weight;
    int vnum,arcnum;
    cout<<"请输入顶点的个数和边的个数:";
    cin>>vnum>>arcnum;
    //  初始化图的代价矩阵
    for(i=0; i<vnum; i++)
        for(j=0; j<vnum; j++)
            arc[i][j]=MAX;
    //  建立图的代价矩阵
    for(k=0; k<arcnum; k++)
    {
        cout<<"请输入边的两个顶点和权值:"<<endl;
        cin>>i>>j>>weight;
        arc[i][j]=weight;
    }
    return vnum;    // 返回顶点个数
}
//  求n个顶点长度多段图的最短路径
int BackPath(int n)
{
    int i,j;
    int cost[n],path[n];    // 存储路径长度和路径
    for(i=1; i<n; i++)
    {
        cost[i]=MAX;    // 初始化路径长度为MAX
        path[i]=-1;
    }
    cost[0]=0;  // 顶点0为源点
    path[0]=-1;
    //  执行填表工作
    for(j=1; j<n; j++)
    {
        //  考察所有入边
        for(i=j-1; i>=0; i--)
        {
            if(arc[i][j]+cost[i]<cost[j])
            {
                cost[j]=arc[i][j]+cost[i];
                path[j]=i;
            }
        }
    }
    cout<<n-1;  // 输出终点
    i=n-1;
    while(path[i]>=0)   // 依次输出path[i]
    {
        cout<<"<-"<<path[i];
        i=path[i];      // 求得路径上顶点i的前一个顶点
    }
    cout<<endl;
    return cost[n-1];   // 返回最短路径长度
}

int main()
{
    int n,m;
    n=CreateGraph();
    m=BackPath(n);
    cout<<m<<endl;
    return 0;
}

测试数据:

10 18
0 1 4
0 2 2
0 3 3
1 4 9
1 5 8
2 4 6
2 5 7
2 6 8
3 5 4
3 6 7
4 7 5
4 8 6
5 7 8
5 8 6
6 7 6
6 8 5
7 9 7
8 9 3

输出: