邻接矩阵 Dijkstra 算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了邻接矩阵 Dijkstra 算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1656字，纯文字阅读大概需要3分钟。

内容图文

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<malloc.h>
#define INF 99999
#define MAXV 100
using namespace std;

typedef struct
{
    int no;
}VertexType;

typedef struct
{
    int edges[100][100];
    int n,e;
    VertexType vexs[100];
}MatGraph;


void CreatMat(MatGraph &g,int A[6][10],int n,int e)
{
    int i,j;
    g.n=n;
    g.e=e;
    for(i=0;i<g.n;i++)
    {
        for(j=0;j<g.n;j++)
        {
            g.edges[i][j]=A[i][j];
        }
    }
}

void DispMat(MatGraph g)
{
    int i,j;
    for(i=0;i<g.n;i++)
    {
        for(j=0;j<g.n;j++)
        {
            if(g.edges[i][j]!=INF)
            {
                printf("%4d",g.edges[i][j]);
            }
            else
            {
                printf("%4s","#");
            }
        }
        cout<<endl;
    }
}

void Dispath(MatGraph g,int dist[],int path[],int S[],int v)
{
    int i,j,k;
    int apath[100];
    int d;
    for(i=0;i<g.n;i++)
    {
        if(S[i]==1&&i!=v)
        {
            printf("From %d to %d DistanceLength: %d\n",v,i,dist[i]);
            d=0;
            apath[d]=i;
            k=path[i];
            if(k==-1)
            {
                cout<<"no distance"<<endl;
            }
            else
            {
                while(k!=v)
                {
                    d++;
                    apath[d]=k;
                    k=path[k];
                }
                d++;
                apath[d]=v;
                cout<<"Distance"<<" "<<v<<" ";
                for(j=d-1;j>=0;j--)
                {
                    cout<<" "<<apath[j]<<" ";
                }
                cout<<"\n"<<endl;
            }
        }

    }
}

void Dijkstra(MatGraph g,int v)
{
    int dist[100];
    int path[100];
    int S[100];
    int Mindis ,i,j,k,u;
    for(i=0;i<g.n;i++)
    {
        dist[i]=g.edges[v][i];
        S[i]=0;
        if(g.edges[v][i]<INF)
        {
            path[i]=v;
        }
        else
        {
            path[i]=-1;
        }
    }
    S[v]=1;
    path[v]=0;
    for(i=0;i<g.n-1;i++)
    {
        Mindis=INF;
        for(j=0;j<g.n;j++)
        {
            if(S[j]==0&&dist[j]<Mindis)
            {
                u=j;
                Mindis=dist[j];
            }
        }
        S[u]=1;
        for(j=0;j<g.n;j++)
        {
            if(S[j]==0)
            {
                if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])
                {
                    dist[j]=dist[u]+g.edges[u][j];
                    path[j]=u;
                }
            }
        }
    }
    Dispath(g,dist,path,S,v);
}

int main()
{
    MatGraph g;
    int A[6][10]={
    {0,5,INF,7,INF,INF}, {INF,0,4,INF,INF,INF},
    {8,INF,0,INF,INF,9}, {INF,INF,5,0,INF,6},
    {INF,INF,INF,5,0,INF}, {3,INF,INF,INF,1,0}};
    CreatMat(g,A,6,10);
    DispMat(g);
    Dijkstra(g,0);
    return 0;
}

 

内容总结

以上是互联网集市为您收集整理的邻接矩阵 Dijkstra 算法全部内容，希望文章能够帮你解决邻接矩阵 Dijkstra 算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---