第13周实验数据结构

13.1 迪杰斯特拉最短路径（一点到其他所有点）

【输入形式】

输入的第一行包含2个正整数n和s，表示图中共有n个顶点，且源点为s。其中n不超过50，s小于n。

以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。

【输出形式】

只有一行，共有n-1个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。

请注意行尾输出换行。

【样例输入】

4 1
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0

【样例输出】

6 4 7

【样例说明】

在本题中，需要按照题目描述中的算法完成迪杰斯特拉算法，并在计算最短路径的过程中将每个顶点是否可达记录下来，直到求出每个可达顶点的最短路径之后，算法才能够结束。 

迪杰斯特拉算法的特点是按照路径长度递增的顺序，依次添加下一条长度最短的边，从而不断构造出相应顶点的最短路径。 

另外需要注意的是，在本题中为了更方便的表示顶点间的不可达状态，可以使用一个十分大的值作为标记。

#include 
using namespace std;
#define MAX 32765
typedef struct graph
{
    int arc[55][55];
    int vexnum;
}Gragh;
int path[50]={0};
int dist[50]={0};
bool flag[50]={0};
void Indist(Gragh gn,int s)//初始化距离数组
{
    for(int i=0;ign.arc[s][m]+gn.arc[m][j])
            {
                gn.arc[s][j]=gn.arc[s][m]+gn.arc[m][j];
                dist[j]=gn.arc[s][j];
                path[j]=m;
            }
        }
    }
    for(int x=0;x>n>>s;
    Gragh gn;
    gn.vexnum=n;
    for(int i=0;i>gn.arc[i][j];
            if(gn.arc[i][j]==0&&i!=j)
                gn.arc[i][j]=MAX;
        }
    }
   
    DIJ(gn,s);
    return 0;
}

13.2：弗洛伊德最短路径（任意两个点的最短路径）

【问题描述】

对于下面一张若干个城市，以及城市之间距离的地图，请采用弗洛伊德算法求出所有城市之间的最短路径。

【输入形式】

顶点个数n，以及n*n的邻接矩阵，其中不可达使用9999代替

【输出形式】

每两个顶点之间的最短路径和经过的顶点

注意：顶点自身到自身的dist值为0，path则为该顶点的编号

【样例输入】

4

9999 4 11 9999

6 9999 2 9999

1 9999 9999 1

9999 3 9999 9999

【样例输出】

from 0 to 0: dist = 0 path:0
from 0 to 1: dist = 4 path:0 1
from 0 to 2: dist = 6 path:0 1 2
from 0 to 3: dist = 7 path:0 1 2 3
from 1 to 0: dist = 3 path:1 2 0
from 1 to 1: dist = 0 path:1
from 1 to 2: dist = 2 path:1 2
from 1 to 3: dist = 3 path:1 2 3
from 2 to 0: dist = 1 path:2 0
from 2 to 1: dist = 4 path:2 3 1
from 2 to 2: dist = 0 path:2
from 2 to 3: dist = 1 path:2 3
from 3 to 0: dist = 6 path:3 1 2 0
from 3 to 1: dist = 3 path:3 1
from 3 to 2: dist = 5 path:3 1 2
from 3 to 3: dist = 0 path:3

#include

using namespace std;
#define MAX 9999
typedef struct gragh
{
           int arc[55][55];
           int vexnum;
}Gragh;
int main()
{
           int path[55][55];
           int dist[55][55];
           int n;
           cin>>n;
           Gragh gn;
           gn.vexnum=n;
           for(int i=0;i>gn.arc[i][j];
                                 if(i==j)
                                            gn.arc[i][j]=0;
                                 dist[i][j]=gn.arc[i][j];
                                 if(i==j||gn.arc[i][j]==MAX)//这里题目要求i==j时路径就是它本身
                                 {
                                            path[i][j]=i;
                                 }
                                 else
                                            path[i][j]=i;
                      }
           }
           for(int k=0;k=0;x--)
                                 {
                                            cout< 
 
13.3关键路径：
 
 
【问题描述】若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向图称为AOE网。如果用AOE网来表示一项工程，那么，仅仅考虑各个子工程之间的优先关系还不够，更多的是关心整个工程完成的最短时间是多少；哪些活动的延期将会影响整个工程的进度，而加速这些活动是否会提高整个工程的效率。因此，通常在AOE网中列出完成预定工程计划所需要进行的活动，每个活动计划完成的时间，要发生哪些事件以及这些事件与活动之间的关系，从而可以确定该项工程是否可行，估算工程完成的时间以及确定哪些活动是影响工程进度的关键。
 【输入形式】第一行输入两个数字，分别表示顶点数和边数；从第二行开始，输入边的信息，格式为（i，j, weight）
 【输出形式】关键路径的总时间（最大路径长度），代表关键活动的边，格式为（顶点1，顶点2），按大小顺序排列
 【样例输入】
 6 8
 0 1 3
 0 2 2
 1 3 2
 1 4 3
 2 3 4
 2 5 3
 3 5 2
 4 5 1
 【样例输出】
 
 
8
 
 
0 2
 
 
2 3
 
 
3 5
 
 
【问题描述】若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向图称为AOE网。如果用AOE网来表示一项工程，那么，仅仅考虑各个子工程之间的优先关系还不够，更多的是关心整个工程完成的最短时间是多少；哪些活动的延期将会影响整个工程的进度，而加速这些活动是否会提高整个工程的效率。因此，通常在AOE网中列出完成预定工程计划所需要进行的活动，每个活动计划完成的时间，要发生哪些事件以及这些事件与活动之间的关系，从而可以确定该项工程是否可行，估算工程完成的时间以及确定哪些活动是影响工程进度的关键。
 【输入形式】第一行输入两个数字，分别表示顶点数和边数；从第二行开始，输入边的信息，格式为（i，j, weight）
 【输出形式】关键路径的总时间（最大路径长度），代表关键活动的边，格式为（顶点1，顶点2），按大小顺序排列
 【样例输入】
 6 8
 0 1 3
 0 2 2
 1 3 2
 1 4 3
 2 3 4
 2 5 3
 3 5 2
 4 5 1
 【样例输出】
 
 
8
 
 
0 2
 
 
2 3
 
 
3 5
 
 
#include
#include
using namespace std;
#define MAX 100
int ve[MAX]={0};
int vl[MAX]={0};
int n,m;
typedef struct arcnode
{
    int data;
    int weight;
    struct arcnode *next=NULL;
}ArcNode;
typedef struct vertexnode
{
    int  data;//顶点
    ArcNode *first=NULL;
}VertexNode;
typedef struct stack
{
    VertexNode point[99];
    int top;
}Stack;
void push(Stack &a,VertexNode point)
{
    if(a.top>=99)
        exit(0);
    else
    {
        a.top++;
        a.point[a.top]=point;
    }
}
void pop(Stack &a,VertexNode &point)
{
    if(a.top==-1)
        exit(0);
    else
    {
        point=a.point[a.top];
        a.top--;
    }
}
//算每个顶点的入度
void Jindegree(int indegree[],VertexNode List[])
{
    for(int i=0;idata]++;
            p=p->next;
        }
    }
}
int main()
{
    cin>>n>>m;//顶点数和边数
    VertexNode point[n];
    for(int i=0;i>x>>y>>weight;
        //cout<<1<data=y;
        p->weight=weight;
        p->next=NULL;

        if(point[x].first==NULL)
        {
            point[x].first=p;
        }
        else
        {
            ArcNode *pp=point[x].first;
            while(pp->next!=NULL)
                pp=pp->next;
            pp->next=p;
        }
    }
    
    int indegree[n]={0};
    Jindegree(indegree,point);//算各点入度
    Stack a,b;//a：存入度为0的顶点。b：存入逆序且修改后的拓扑排序
    a.top=-1;b.top=-1;
    for(int i=0;idata;
            if(--indegree[k]==0)
                push(a,point[k]);
            if(ve[j.data]+t->weight>ve[k])//计算每个顶点的最早发生时间
                ve[k]=ve[j.data]+t->weight;
            t=t->next;
        }
    }
    //计算每个顶点的最晚发生时间，计算每个活动的最早和最晚发生时间
    for(int i=0;idata;
            if(vl[g]-d->weightweight;
            d=d->next;
        }
    }
    cout<data]-f->weight;
            if(ei==li)
            cout<data<next;
        }
    }
}

 
 
注释：先求最早发生事件，再求最晚发生事件，最后根据前面两个求出每个活动的最早发生时间和最晚发生时间，然后活动这两个时间相同的就是关键路径。