5 数据结构课程设计小组任务5：Dijkstra算法的设计

问题描述 :

在使用图的邻接矩阵ADT的基础上，设计Dijkstra算法，用以解决单源最短路径问题，并以文本形式输出从源点到其余各个顶点的路径以及路径长度。将此算法加入到邻接矩阵ADT中，在邻接矩阵ADT中提供一个公有的成员函数Dijkstra。

提示：

（1）单源最短路径问题：已知有向带权图(简称有向网)G=(V，E)，找出从某个源点s∈V到V中其余各顶点的最短路径。

（2）目的：设一有向图G=（V, E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。应按路径“长度” 递增的次序，逐步产生最短路径。

（3）Dijkstra算法的基本步骤：设V0是起始源点，U = 已求得最短路径终点集合。V-U = 未确定最短路径的顶点的集合，初始时 U ={V0}。

1）“长度”最短的最短路径是边数为1的长度最小的路径。
2）下一条“长度”最短的路径：
① Vi  V - U ，先求出V0 到Vi 中间只经 U 中结点的最短路径；
② 上述最短路径中长度最小者即为下一条长度最短的路径；
③ 将所求最短路径的终点加入U 中；
3）重复2）直到求出所有的最短路径。

（4）实现方法：

1）图用带权邻接矩阵存储ad[][]；
2）数组dist[]存放当前找到的从源点V0到每个终点的最短路径长度，其初态为图中直接路径权值；
3）数组pre[]表示从V0到各终点的最短路径上，此顶点的前一顶点的序号；若从V0到某终点无路径，则用0作为其前一顶点的序号。

参考函数原型：

（1）//Dijkstra算法（成员函数）

template<class TypeOfVer, class TypeOfEdge>
bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::Dijkstra( int u, TypeOfEdge *dist, int *pre); // u：源点的位序

（2）辅助函数

//最短路径输出（用户函数）

template<class TypeOfVer, class TypeOfEdge>
void searchPath(TypeOfVer *ver, int *prev, TypeOfEdge *dist, int v, int u); // ver：输入的顶点集 v：源点的位序 u：终点的位序

输入说明 :

第一行：图的类型

第二行：顶点数

第三行：顶点集

第四行：无边标记

第五行：边数

第六行：边集

第七行：权集

第八行：源点位序

输出说明 :

第一行：顶点集

 空行

第二行：图的邻接矩阵

 空行

第三行：dist数组的初值

第四行：pre数组的初值

 空行

第五行：dist数组的值

第六行：pre数组的值

空行

第七行：源点到其余各顶点的最短路径及最短路径长度（输出格式参见测试数据）

输入范例 :

DN
7
V1 V2 V3 V4 V5 V6 V7
99
10
0 1
0 2
0 4
0 6
1 5
1 6
2 3
3 4
4 5
5 6
13 8 30 32 9 7 5 6 2 17
0
输出范例 :

V1 V2 V3 V4 V5 V6 V7

99 13 8 99 30 99 32
99 99 99 99 99 9 7
99 99 99 5 99 99 99
99 99 99 99 6 99 99
99 99 99 99 99 2 99
99 99 99 99 99 99 17
99 99 99 99 99 99 99

0 13 8 99 30 99 32
0 1 1 0 1 0 1

0 13 8 13 19 21 20
0 1 1 3 4 5 2

<(0,V1),(1,V2)>,13
<(0,V1),(2,V3)>,8
<(0,V1),(2,V3),(3,V4)>,13
<(0,V1),(2,V3),(3,V4),(4,V5)>,19
<(0,V1),(2,V3),(3,V4),(4,V5),(5,V6)>,21
<(0,V1),(1,V2),(6,V7)>,20

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

template <class TypeOfVer, class TypeOfEdge>
class adjmatrix_graph {
private:
    int Vers;        //顶点数 
    int Edges;       //边数 
    vector<vector<TypeOfEdge>> edge;  //存放邻接矩阵（TypeOfEdge表示顶点关系类型。对于无权图，用1或0，表示相邻否；对于带权图，则为权值类型） 
    vector<TypeOfVer> ver;    //存放结点值 
    TypeOfEdge noEdge;  //邻接矩阵中的∞的表示值
    string GraphKind;   //图的种类标志 
    void DFS(int u, int& num, vector<int>& visited) //DFS遍历（递归部分）
    {
        if (num != Vers)cout << "->";
        cout << ver[u];
        if (num == 0)return;
        visited[u] = 1;
        num--;
        if (num == 0)return;
        int v, w;
        GetFirstAdjVex(u, v);
        while (v != -1)
        {
            if (visited[v])
            {
                GetNextAdjVex(u, v, w);
                v = w;
            }
            else DFS(v, num, visited);
        }
    }
    bool CheckRoute(int u, int targe, vector<int>& visited) //检查两个结点之间是否有路径存在（递归部分，私有成员函数） 
    {
        visited[u] = 1;
        if (visited[targe])return true;
        int v, w;
        GetFirstAdjVex(u, v);
        while (v != -1)
        {
            if (visited[v])
            {
                GetNextAdjVex(u, v, w);
                v = w;
            }
            else CheckRoute(v, targe, visited);
        }
        if (visited[targe])return true;
        else return false;
    }
public:
    //构造函数构造一个只有结点没有边的图。4个参数的含义：图的类型、结点数、结点值和邻接矩阵中表示结点间没有边的标记（无权图：0，有权图：输入参数定）
    adjmatrix_graph(string& kd, int vSize, vector<TypeOfVer>& d, TypeOfEdge noEdgeFlag)
    {
        GraphKind = kd;
        Vers = vSize;
        ver = d;
        noEdge = noEdgeFlag;
        edge.resize(vSize);
        for (int i = 0;i < vSize;i++)
            edge[i].resize(vSize);
        fill(edge.begin(), edge.end(), noEdge);
    }
    //构造函数构造一个无权图。5个参数的含义：图的类型、结点数、边数、结点集和边集 
    adjmatrix_graph(string& kd, int vSize, int eSize, vector<TypeOfVer>& d, vector<vector<int>>& e)
    {
        GraphKind = kd;
        Vers = vSize;
        ver = d;
        Edges = eSize;
        noEdge = 0;
        edge.resize(vSize);
        for (int i = 0;i < vSize;i++)
            edge[i].resize(vSize);
        for (int i = 0;i < vSize;i++)
        {
            for (int j = 0;j < vSize;j++)
            {
                edge[i][j] = e[i][j];
            }
        }
        if (GraphKind == "UDG")
        {
            for (int i = 0;i < vSize;i++)
                for (int j = 0;j < vSize;j++)
                    if (edge[i][j] != noEdge)
                        edge[j][i] = edge[i][j];
        }
    }
    //构造函数构造一个有权图。7个参数的含义：图的类型、结点数、边数、无边标记、结点集、边集、权集
    adjmatrix_graph(string& kd, int vSize, int eSize, TypeOfEdge noEdgeFlag, vector<TypeOfVer>& d, vector<vector<int>>& e, vector<TypeOfEdge>& w)
    {
        this->GraphKind = kd;
        Vers = vSize;
        ver = d;
        noEdge = noEdgeFlag;
        Edges = eSize;
        edge.resize(vSize);
        for (int i = 0;i < vSize;i++)
            edge[i].resize(vSize);
        int count = 0;
        for (int i = 0;i < vSize;i++)
        {
            for (int j = 0;j < vSize;j++)
            {
                if (e[i][j] != 0)
                {
                    edge[i][j] = w[count++];
                }
                else edge[i][j] = noEdge;
            }
        }
        if (GraphKind == "UDN")
        {
            for (int i = 0;i < vSize;i++)
                for (int j = 0;j < vSize;j++)
                    if (edge[i][j] != noEdge)
                        edge[j][i] = edge[i][j];
        }
        e.clear();
        w.clear();
    }
    ~adjmatrix_graph() //析构函数 
    {

    }

    bool GraphisEmpty() { return Vers == 0; }  //判断图空否
    string GetGraphKind() { return GraphKind; }
    int GetVerNum() { return Vers; }    //取得当前顶点数 
    int GetEdgeNum() { return Edges; }  //取得当前边数 
    TypeOfEdge GetnoEdge() { return noEdge; }

    bool Print()  //输出邻接矩阵 
    {
        if (GraphisEmpty())return false;
        cout << GraphKind << endl;
        for (int i = 0;i < Vers - 1;i++)
            cout << ver[i] << " ";
        cout << ver[Vers - 1] << endl << endl;
        for (int i = 0;i < Vers;i++)
        {
            for (int j = 0;j < Vers;j++)
            {
                cout << edge[i][j] << " ";
            }
            cout << endl;
        }
        return true;
    }
    bool PrintMatrix()  //输出邻接矩阵 
    {
        if (GraphisEmpty())return false;
        for (int i = 0;i < Vers;i++)
        {
            for (int j = 0;j < Vers;j++)
            {
                cout << edge[i][j] << " ";
            }
            cout << endl;
        }
        return true;
    }
    bool PrintGraphKind()
    {
        if (GraphisEmpty())return false;
        cout << GraphKind << endl;
        return true;
    }
    bool PrintVers()
    {
        if (GraphisEmpty())return false;
        cout << Vers << endl;
        return true;
    }
    bool PrintVer()
    {
        if (GraphisEmpty())return false;
        cout << ver[0];
        for (int i = 1;i < Vers;i++)
            cout << " " << ver[i];
        cout << endl;
        return true;
    }
    bool PrintEdges()
    {
        if (GraphisEmpty())return false;
        cout << Edges << endl;;
        return true;
    }

    bool GetVer(int u, TypeOfVer& data) //取得G中指定顶点的值 
    {
        if (u >= Vers)return false;
        data = ver[u];
        return true;
    }
    vector<TypeOfVer> GetVer() { return ver; }
    int GetFirstAdjVex(int u, int& v) //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1 
    {
        if (u >= Vers)return v = -1;
        v = -1;
        for (int i = 0;i < Vers;i++)
        {
            if (edge[u][i] != noEdge) {
                v = i;
                break;
            }
        }
        return v;
    }
    int GetNextAdjVex(int u, int v, int& w) //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
    {
        if (u >= Vers || v >= Vers)return w = -1;
        w = -1;
        for (int i = v + 1;i < Vers;i++)
        {
            if (edge[u][i] != noEdge) {
                w = i;
                break;
            }
        }
        return w;
    }
    
    bool PutVer(int u, TypeOfVer data) //对G中指定顶点赋值 
    {
        if (u >= Vers)return false;
        ver[u] = data;
        return true;
    }
    int LocateVer(TypeOfVer data) //返回G中指定顶点的位置 
    {
        for (int i = 0;i < Vers;i++)
        {
            if (ver[i] == data)return i;
        }
        return -1;
    }
    bool InsertVer(TypeOfVer& data) //往G中添加一个顶点
    {
        ver.push_back(data);
        edge.push_back(vector<TypeOfEdge>(Vers, noEdge));
        Vers++;
        for (int i = 0;i < Vers;i++)
        {
            edge[i].push_back(noEdge);
        }
        return true;
    }
    bool Insert_Edge(int u, int v) //无权图插入一条边
    {
        if (u >= Vers || v >= Vers)return false;
        else edge[u][v] = 1;
        if (GraphKind == "UDG" || GraphKind == "UDN")
            edge[v][u] = 1;
        return true;
    }
    bool Insert_Edge(int u, int v, TypeOfEdge w) //有权图插入一条边
    {
        if (u >= Vers || v >= Vers)return false;
        else edge[u][v] = w;
        if (GraphKind == "UDG" || GraphKind == "UDN")
            edge[v][u] = w;
        return true;
    }
    bool DeleteVer(TypeOfVer& data) //往G中删除一个顶点
    {
        int n = LocateVer(data);
        if (n == -1)return false;
        ver.erase(ver.begin() + n);
        for (int i = 0;i < Vers;i++)
            edge[i].erase(edge[i].begin() + n);
        edge.erase(edge.begin() + n);
        Vers--;
        return true;
    }
    bool Delete_Edge(int u, int v) //无权图删除一条边 
    {
        if (u >= Vers || v >= Vers)
            return false;
        if (edge[u][v] == noEdge)return false;
        edge[u][v] = noEdge;
        if (GraphKind == "UDG" || GraphKind == "UDN")
            edge[v][u] = noEdge;
        Edges--;
        return true;
    }
    bool Delete_Edge(int u, int v, TypeOfEdge& w) //有权图删除一条边 
    {
        if (u >= Vers || v >= Vers)
            return false;
        if (edge[u][v] == noEdge)return false;
        w = edge[u][v];
        edge[u][v] = noEdge;
        if (GraphKind == "UDG" || GraphKind == "UDN")
            edge[v][u] = noEdge;
        Edges--;
        return true;
    }
    void DFS_Traverse(int u) //DFS遍历（外壳部分）
    {
        if (u >= Vers)return;
        vector<int>visit(Vers);
        int num = Vers;
        DFS(u, num, visit);
    }
    void BFS_Traverse(int u) //BFS遍历
    {
        queue<int>q;
        vector<int>visit(Vers);
        q.push(u);
        int v, w;
        bool first = true;
        visit[u] = 1;
        while (!q.empty())
        {
            if (!first)cout << "->";
            first = false;
            u = q.front();
            cout << ver[u];
            q.pop();
            GetFirstAdjVex(u, v);
            while (v != -1)
            {
                if (!visit[v])
                {
                    q.push(v);
                    visit[v] = 1;
                }
                GetNextAdjVex(u, v, w);
                v = w;
            }
        }
    }

    int Get_InDegree(int u)//求有向图指定顶点的入度 
    {
        if (u >= Vers)return -1;
        if (GraphKind == "UDG" || GraphKind == "UDN")return -1;
        int n = 0;
        for (int i = 0;i < Vers;i++)
            if (edge[i][u] != noEdge)n++;
        return n;
    }
    int Get_OutDegree(int u)//求有向图指定顶点的(出)度 
    {
        if (u >= Vers)return -1;
        int n = 0;
        for (int i = 0;i < Vers;i++)
            if (edge[u][i] != noEdge)n++;
        return n;
    }
    bool ExistEdge(int u, int v)//检查指定2个顶点是否是邻接顶点 
    {
        if (u >= Vers || v >= Vers)return false;
        if (edge[u][v] != noEdge)return true;
        return false;
    }
    bool CheckRoute(int u, int v)//检查两个结点之间是否有路径存在（外壳部分，公有成员函数） 
    {
        if (u >= Vers || v >= Vers)return false;
        vector<int>visit(Vers);
        return CheckRoute(u, v, visit);
    }

    TypeOfEdge GetEdgeWeight(int u, int v) { return edge[u][v]; }
    //Dijkstra算法（成员函数）
    bool Dijkstra(int u,vector<TypeOfEdge>& dist, vector<int> &pre) // u：源点的位序 
    {
        if (u < 0 || u >= Vers)return false;
        vector<int>vis(Vers, 0);
        vis[u] = 1;
        for (int i = 0;i < Vers;i++)
        {
            int min = 0x3f3f3f3f;
            int minIndex = -1;
            for (int i = 0;i < Vers;i++)
            {
                if (min > dist[i] && !vis[i])
                {
                    minIndex = i;
                    min = dist[i];
                }
            }
            if (minIndex == -1)break;
            vis[minIndex] = 1;
            int v, w;
            GetFirstAdjVex(minIndex, v);
            while (v != -1)
            {
                if (dist[v] > dist[minIndex] + edge[minIndex][v])
                {
                    dist[v] = dist[minIndex] + edge[minIndex][v];
                    pre[v] = minIndex + 1;
                }
                GetNextAdjVex(minIndex, v, w);
                v = w;
            }
        }
    }
};

template <class TypeOfVer>
void input(int& vSize, int& eSize, vector<TypeOfVer>& d, vector<vector<int>>& e)
{
    cin >> vSize;
    d.resize(vSize);
    for (int i = 0;i < vSize;i++)
    {
        cin >> d[i];
    }
    cin >> eSize;
    e.resize(vSize);
    for (int i = 0;i < vSize;i++)
        e[i].resize(vSize);
    int a, b;
    for (int i = 0;i < eSize;i++)
    {
        cin >> a >> b;
        e[a][b] = 1;
    }
}

template <class TypeOfVer, class TypeOfEdge>
void input(int& vSize, int& eSize, TypeOfEdge &NoEdgeflag,vector<TypeOfVer>& d, vector<vector<int>>& e, vector<TypeOfEdge>& w)
{
    cin >> vSize;
    d.resize(vSize);
    for (int i = 0;i < vSize;i++)
    {
        cin >> d[i];
    }
    cin >> NoEdgeflag;
    cin >> eSize;
    e.resize(vSize);
    for (int i = 0;i < vSize;i++)
        e[i].resize(vSize);
    int a, b;
    for (int i = 0;i < eSize;i++)
    {
        cin >> a >> b;
        e[a][b] = 1;
    }
    w.resize(eSize);
    for (int i = 0;i < eSize;i++)
        cin >> w[i];
}

//最短路径输出（用户函数）
template<class TypeOfVer, class TypeOfEdge>
void searchPath(vector<TypeOfVer>& ver, vector<int>& prev, vector<TypeOfEdge>& dist, int v, int u)  // ver：输入的顶点集  v：源点的位序  u：终点的位序 
{
    int temp = u;
    if (prev[u] == 0 || u == v)return;
    stack<int>s;
    while (u != -1)
    {
        s.push(u);
        u = prev[u] - 1;
    }
    cout << "<";
    if (!s.empty())cout << "(" << s.top() << "," << ver[s.top()] << ")";
    s.pop();
    while (!s.empty())
    {
        cout << ",";
        cout << "(" << s.top() << "," << ver[s.top()] << ")";
        s.pop();
    }
    cout << ">," << dist[temp] << endl;
}

template <class TypeOfVer, class TypeOfEdge>
void runner(adjmatrix_graph<TypeOfVer, TypeOfEdge>& matrix)
{
    int n = matrix.GetVerNum();
    TypeOfEdge noEgde = matrix.GetnoEdge();
    vector<TypeOfEdge>dist(n, noEgde);
    vector<int>pre(n, 0);
    int u, v, w;
    cin >> u;
    pre[u] = 0;
    dist[u] = 0;
    matrix.GetFirstAdjVex(u, v);
    while (v != -1)
    {
        dist[v] = matrix.GetEdgeWeight(u, v);
        pre[v] = u + 1;
        matrix.GetNextAdjVex(u, v, w);
        v = w;
    }
    matrix.PrintVer();
    cout << endl;
    matrix.PrintMatrix();
    cout << endl;
    for (auto x : dist)
        cout << x << " ";
    cout << endl;
    for (auto x : pre)
        cout << x << " ";
    cout << endl << endl;
    matrix.Dijkstra(u, dist, pre);
    for (auto x : dist)
        cout << x << " ";
    cout << endl;
    for (auto x : pre)
        cout << x << " ";
    cout << endl << endl;
    vector<TypeOfVer> ver = matrix.GetVer();
    for (int i = 0;i < n;i++)
        searchPath(ver, pre, dist, u, i);

}

int main()
{
    typedef string TypeOfVer;
    typedef int TypeOfEdge;
    int vSize = 0, eSize = 0;
    vector<vector<int>>e;
    vector<TypeOfVer> d;
    TypeOfEdge noEdgeFlag;
    vector<TypeOfEdge>w;

    string str;
    cin >> str;
    if (str == "DG" || str == "UDG")
    {
        input(vSize, eSize, d, e);//无权图的构造
        adjmatrix_graph<TypeOfVer, TypeOfEdge> matrix(str, vSize, eSize, d, e);
        runner(matrix);
    }
    else {
        input(vSize, eSize, noEdgeFlag, d, e, w);//有权图的构造
        adjmatrix_graph<TypeOfVer, TypeOfEdge> matrix(str, vSize, eSize, noEdgeFlag, d, e, w);
        runner(matrix);
    }
    return 0;
    
}

微信号公众号搜索：澜莲小哥

个人博客：澜莲的博客

力扣：https://leetcode-cn.com/u/g-l-/

微博：澜澜沧海水