图，最短路径，好难，求解

Question

路径存在
对一个包含 N 个顶点的有向图 G(V, E) 用邻接表进行存储，其中顶点以数组保存。对于该有向图类 adjListGraph，
要求增加一个成员函数 existPath，对于图中的任两个顶点 i, j，检查它们之间是否有路径存在。如有，输出其中最小的一条路径。
如无，输出字符串 "false"。(40')

对于最小路径，首先判断长度，输出较小长度的路径，若存在多条长度相同的路径，则输出路径顺序中结点编号较小的路径。例如路径 6 1 5 4 和 6 2 3 4，应选择前者输出。

注：图中可能存在环。

要求：在文件头部说明新增成员函数的设计思路，并分析时间复杂度分析。(10')

输入描述
第1行输入顶点个数 N，N 为正整数。

第2行输入有向边信息，边的起点和终点分别为顶点的编号，编号间以逗号相隔，边之间以空格相隔。

第3行输入路径起点和终点的编号，以空格相隔。

输出描述
输出路径检查的结果。

输入举例
6
1,3 2,3 1,4 3,5 2,5 4,2 5,6 3,6
4 6
输出举例
4 2 3 6

#include<bits/stdc++.h>
using namespace std;
template<class elemType>
class linkQueue
{
    private:
        struct node
        {
            elemType data;
            node *next;
            node( elemType &x,node *N=NULL)
            {
                data=x;
                next=N;
            }
            node():next(NULL){}
            ~node(){}
        };
    node *front,*rear;
    public:
        linkQueue();
        ~linkQueue();
        bool isEmpty() ;
        elemType deQueue();
        void enQueue( elemType &x);
};

template<class elemType>
bool linkQueue<elemType>::isEmpty() 
{
    return front==NULL;
}
template<class elemType>
linkQueue<elemType>::linkQueue()
{
    front=rear=NULL;
}
template<class elemType>
linkQueue<elemType>::~linkQueue()
{
    node *tmp;
    while(front!=NULL)
    {
        tmp=front;
        front=front->next;
        delete tmp;
    }
}
template<class elemType>
void linkQueue<elemType>::enQueue(elemType &x)
{
    if(rear==NULL)
        front=rear=new node(x);
    else
        rear=rear->next=new node(x);
}
template<class elemType>
elemType linkQueue<elemType>::deQueue()
{
    node *tmp=front;
    elemType value=front->data;
    front=front->next;
    if(front==NULL)
        rear=NULL;
    delete tmp;
    return value;
}
template<class TypeOfVer,class TypeOfEdge>
class adjListGraph
{
    public:
        adjListGraph(int vSize);
        void insert(TypeOfVer x,TypeOfVer y,TypeOfEdge w);
        //void remove(TypeOfVer x,TypeOfVer y);
        //bool exist(TypeOfVer x,TypeOfVer y)const;
        bool checkRoute(int start,int end);
        //void existPath(int start,int end);
        //~adjListGraph();
        void unweightedShortDistance(TypeOfVer start,TypeOfVer end,TypeOfEdge noEdge);
    private:
        int Vers,Edges;
        struct edgeNode 
        {
            int end;
            TypeOfEdge weight;
            edgeNode *next;
            edgeNode(int e,TypeOfEdge w,edgeNode *n=NULL)
            {
                end=e;
                weight=w;
                next=n;
            }
        };
        struct verNode
        {
            TypeOfVer ver;
            edgeNode *head;
            verNode(edgeNode *h=NULL)
            {
                head=h;
            }
        };
        verNode *verList;
        int find(TypeOfVer v)const
        {
            for(int i=0;i<Vers;i++)
            {
                if(verList[i].ver==v)
                {
                    return i;
                }
            }
        }
        bool checkRoute(int start,int end,bool visited[]);
        //void existPath(int start,int end,bool visited[]);
        void printPath(int start,int end,int prev[]);
};
template<class TypeOfVer,class TypeOfEdge>
adjListGraph<TypeOfVer,TypeOfEdge>::adjListGraph(int vSize)
{
    Vers=vSize;
    Edges=0;
    verList=new verNode[vSize];
    for(int i=0;i<Vers;i++)
    {
        verList[i].ver=i+1;
    }
}
/*template<class TypeOfVer,class TypeOfEdge>
adjListGraph<TypeOfVer,TypeOfEdge>::~adjListGraph()
{
    int i;
    edgeNode *p;
    for(i=0;i<Vers;i++)
    {
        while((p=verList[i].head)!=NULL)
        {
            verList[i].head=p->next;
            delete p;
        }
    }
    delete []verList;
}*/
template<class TypeOfVer,class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::insert(TypeOfVer x,TypeOfVer y,TypeOfEdge w)
{
    int u=find(x);
    int v=find(y);
    verList[u].head=new edgeNode(v,w,verList[u].head);
    ++Edges;
}
template<class TypeOfVer,class TypeOfEdge>
bool adjListGraph<TypeOfVer,TypeOfEdge>::checkRoute(int start,int end)
{
    bool *visited=new bool[Vers];
    int startNo,endNo;
    for(int i=0;i<Vers;i++)
    {
        visited[i]=false;
    }
    for(startNo=0;startNo<Vers;startNo++)
    {
        if(verList[startNo].ver==start)break;
    }
    //if(startNo==Vers)return false;
    for(endNo=0;endNo<Vers;endNo++)
    {
        if(verList[endNo].ver==end)break;
    }
    //if(endNo==Vers)return false;
    return checkRoute(startNo,endNo,visited);
}
template<class TypeOfVer,class TypeOfEdge>
bool adjListGraph<TypeOfVer,TypeOfEdge>::checkRoute(int start,int end,bool visited[])
{
    edgeNode *p=verList[start].head;
    bool flag=0;
    visited[start]=true;
    while(p!=NULL)
    {
        if(p->end==end)return true;
        if(!visited[p->end])
        {
            flag=checkRoute(p->end,end,visited);
            if(flag)return true;
        }
        p=p->next;
    }
    //cout<<"okok";
    return false;
}
/*template<class TypeOfVer,class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::existPath(int start,int end)
{
    bool *visited=new bool[Vers];
    for(int i=0;i<Vers;i++)
    {
        visited[i]=false;
    }
    existPath(start,end,visited);
}
static int L[100],o=0;
template<class TypeOfVer,class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::existPath(int start,int end,bool visited[])
{
    edgeNode *p=verList[start].head;
    L[o]=start;
    o++;
    //cout<<start;
    visited[start]=true;
    while(p!=NULL)
    {
        if(p->end==end)
        {
            L[o]=end;
            o++;
            //cout<<"okok";
            break;
        }
        else if(!visited[p->end]&&checkRoute(p->end,end))
        {
            existPath(p->end,end,visited);
        }
        p=p->next;
    }
}*/
template<class TypeOfVer,class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::unweightedShortDistance(TypeOfVer start,TypeOfVer end,TypeOfEdge noEdge)
{
    linkQueue<int> q;
    TypeOfEdge *distance=new TypeOfEdge[Vers];
    int *prev=new int[Vers];
    int u,sNo;
    edgeNode *p;
    for(int i=0;i<Vers;i++)
    {
        distance[i]=noEdge;
    }
    sNo=find(start);
    distance[sNo]=0;
    prev[sNo]=sNo;
    q.enQueue(sNo);
    while(!q.isEmpty())
    {
        u=q.deQueue();
        for(p=verList[u].head;p!=NULL;p=p->next)
        {
            if(distance[p->end]==noEdge)
            {
                distance[p->end]=distance[u]+1;
                prev[p->end]=u;
                q.enQueue(p->end);
            }
        }
    }
    //cout<<prev[6]<<endl; 
    printPath(sNo,end-1,prev);
}
template<class TypeOfVer,class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::printPath(int start,int end,int prev[])
{
    if(start==end)
    {
        cout<<verList[start].ver;
        return;
    }
    printPath(start,prev[end],prev);
    cout<<' '<<verList[end].ver;
}
//int **Arr;
int main()
{
    int n;
    cin>>n;
    string str;
    getline(cin,str);
    getline(cin,str);
    //cout<<str;
    int x,y;
    cin>>x>>y;
    //cout<<x<<y;
    adjListGraph<int,int> A(n);
    int k=0;
    for(int i=0;i<str.size();i++)
    {
        if(str[i]==',')
        {
            k++;
        }
    }
    //cout<<k;
    for(int i=0;i<k;i++)
    {
        int t1,t2,u,v;
        u=4*i;v=4*i+2;
        t1=str[u]-'0';
        t2=str[v]-'0';
        //cout<<t1<<" "<<t2<<endl;
        A.insert(t1,t2,0);
    }    
    bool flg=A.checkRoute(x,y);
    //cout<<flg;
    if(flg)
    {
        A.unweightedShortDistance(x,y,-1);
    }
    else
    {
        cout<<"false";
    }
}

这个是自己写的但是没有办法满足“若存在多条长度相同的路径，则输出路径顺序中结点编号较小的路径”

Answer 1

#include<bits/stdc++.h>
using namespace std;
vector<int> road[10001];    // 储存每个点能通向的其他点
vector<int> finds,key;       // 查找过错 and 储存答案
bool flag = false;          // 查找结果
bool op[10001]={false};             // 避免查询过程重复路径
void find_RoadMin(int x, int y);
int main()
{
    int N,num,a,b;             // 总点数,边个数,俩个边
    cin >> N >> num;

    // 数据读入
    while (num--){
        cin >> a >> b;
        road[a].push_back(b);
//        road[b].push_back(a);  // 注意无向的话俩个顶点应该是互通的,可你这道题是不互通
    }

    //  开始查询
    cin >> a >> b;
    find_RoadMin(a,b);

    //  答案输出
    if(flag){
        cout << key[0];
        for(int z=1;z<key.size();z++) cout << " " << key[z];
    }else cout << "false" << endl;
    return 0;
}

void find_RoadMin(int x, int y){
    if(op[x]) return;
    op[x] = true;
    finds.push_back(x);
    if(x==y)
    {
//        cout<< "*****";  // 解开注释观察测试数据
        if(finds.size()<key.size() || key.empty() ) {
            key.assign(finds.begin(),finds.end());  // key复制finds
        }
        else if(finds.size()==key.size()){
            for(int z=0;z<finds.size();z++){
                if(key[z]==finds[z]) continue;
                if(key[z]>finds[z]) key.assign(finds.begin(),finds.end());  // key下一个数比finds的大
                break;
            }
        }
        flag = true;
    }

//    解开注释观察每次测试数据变换
//    for(int z:finds) cout << z << " ";
//    cout << endl;

    for(int z:road[x])  find_RoadMin(z,y);
    finds.pop_back();
    op[x] = false;
}