算法实验题7.3 最长简单路径问题
«问题描述：
试设计一个算法，对于给定的带权有向图，计算出该图中指定顶点为起点和终点的最长
简单路，并分析算法的计算时间复杂性。
«实验任务：
对于给定的图G 和G 中的2 个顶点v和w，计算从v到w的最长简单路。
«数据输入：
由文件input.txt 给出输入数据。第1 行有2 个正整数n 和m，表示给定的图G 有n 个
顶点和m条边，顶点编号为1，2，…，n。接下来的m行中，每行有3 个正整数u,v,w，表
示图G 的一条边(u,v)及其边权w。第m+1 行是一个正整数k，表示要计算k 对顶点间的最
长简单路。接下来的k 行中，每行有2 个正整数s 和t，表示要计算顶点对s 和t 间的最长
简单路。
«结果输出:
将计算出的各顶点对间的最长简单路长依次输出到文件output.txt。如果不存在满足要
求的简单路，则输出-1。
输入文件示例 输出文件示例
input.txt          output.txt
7 10             102
1 2 –5            103
1 3 –6            -1
1 6 1
1 7 13
2 3 100
3 4 1
3 5 1
4 5 1
5 6 1
5 7 1
3
2 5
2 6
2 1

下面就是代码拉：
#include <stdio.h>
#define MAX 101
typedef struct Graph
{
    int arc[MAX][MAX];
    int v_num,a_num;
}Graph;

typedef struct DistType
{
    int Length;
    int Flag;
}DistType;

int  GetPath(Graph g,int Source,int Dest)
{
    int i,Count=0;
    int intMax=0;
    int intPos;
    DistType dist[MAX];
    int path[MAX];//前趋节点

    for(i=1;i<=g.v_num;i++)
    {
        dist[i].Flag =0;
        dist[i].Length =g.arc[Source][i];
        if(g.arc[Source][i]!=0) 
            path[i]=Source;
        else
            path[i]=-1;
    }
    dist[Source].Length=0;
    dist[Source].Flag=1;
    while(Count<g.v_num)
    {
        intMax=-10000;
        intPos=1;
        for(i=1;i<=g.v_num;i++)
        {
            if(dist[i].Flag==0&&dist[i].Length>intMax)
            {
                intMax=dist[i].Length;
                intPos=i;
            }
        }
        dist[intPos].Flag =1;
        Count++;
        for(i=1;i<=g.v_num;i++)
        {
            if(dist[i].Flag ==0&&dist[i].Length+g.arc[intPos][i]>dist[i].Length)
            {
                dist[i].Length=dist[i].Length +g.arc[intPos][i];
                path[i]=intPos;
            }
        }
    }
    return dist[Dest].Length;
}
void main()
{
    int t,k,l,i,j;
    int Source,Dest;
    int ivex,jvex;
    Graph g;
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    scanf("%d %d",&g.v_num,&g.a_num);
    for(i=1;i<=g.v_num;i++)
        for(j=1;j<=g.v_num;j++)
            g.arc[i][j]=0;         
    for(j=1;j<=g.a_num;j++)
    {
        scanf("%d %d",&ivex,&jvex);
        scanf("%d",&g.arc[ivex][jvex]);
        printf("\n");
    }
    scanf("%d",&k);
    for(t=1;t<=k;t++)
    {
        scanf("%d %d",&Source,&Dest);
        printf("%d\n",GetPath(g,Source,Dest));
    }

}