dijkstra.cpp

Dijkstra算法 邻接表向量实现（求最短路径及具体走法）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<vector>
using namespace std;

#define  MAX_DOTNUM 1000
#define MAX_INT 999999999

struct node 
{

    int v;
    int w;
};
vector<node>myvector[MAX_DOTNUM];
stack<int>mystack;
int visit[MAX_DOTNUM];
int dis[MAX_DOTNUM];
int pre[MAX_DOTNUM];
int n;

void Dij_plus(int s)
{
    int i,j;
    memset(visit,0,sizeof(visit));
    memset(pre,0,sizeof(pre));
    for(i=1;i<=n;i++)
    {
        if(i==s)
        {
            dis[i]=0;
            continue;
        }
        dis[i]=MAX_INT;
    }
    for(i=0;i<myvector[s].size();i++)//vector支持下标运算
    {
        int v;
        v=myvector[s][i].v;
        dis[v]=myvector[s][i].w;
    }
    visit[s]=1;
    int temp=MAX_INT;
    int mark;
    for(i=1;i<=n;i++)
    {
        pre[i]=-1;
    }
    for(i=0;i<myvector[s].size();i++)
    {
        int v=myvector[s][i].v;
        if(visit[v]!=1)
            pre[v]=s;
    }
    for(j=1;j<=n-1;j++)
    {

        temp=MAX_INT;
        for(i=1;i<=n;i++)
        {
            if(visit[i]!=1&&dis[i]<temp)
            {

                temp=dis[i];
                mark=i;
            }
        }
    
        visit[mark]=1;
        for(i=0;i<myvector[mark].size();i++)
        {
            int v=myvector[mark][i].v;
            if(visit[v]!=1&&myvector[mark][i].w+dis[mark]<dis[v])
            {
                dis[v]=myvector[mark][i].w+dis[mark];
                pre[v]=mark;
            }
        }
    }
}


int main ()
{
    int s;
    int i;
    cout<<"请输入顶点的数目:";
    cin>>n;
    cout<<"请输入源点s:";
    cin>>s;
    cout<<"请输入边和权,并以0,0,0结束(u,v,w):"<<endl;
    for(i=1;;i++)
    {
        int u,v,w;
        cout<<"请输入第"<<i<<"条边:";
        cin>>u>>v>>w;
        if(u==0&&v==0&&w==0)
            break;
        node temp;
        temp.v=v;
        temp.w=w;
        myvector[u].push_back(temp);
    }
    Dij_plus(s);
    while(!mystack.empty())
    {
        mystack.pop();
    }
    int temp;
    for(i=1;i<=n;i++)
    {
        
        if(i==s)
            continue;
        else if(pre[i]==-1)
        {
            
            printf("从%d号点到%d号点没有通路\n",s,i);
            continue;
        }
        printf("从%d号点到%d号点的通路为:",s,i);
        temp=i;
        while(temp!=s)
        {
            
            mystack.push(temp);
            temp=pre[temp];
        }
        mystack.push(s);
        while(mystack.size()!=0)
        {
            printf("%d ",mystack.top());
            mystack.pop();
        }
        printf("\n");
    }
    system("pause");
    return 0;
}