Dijkstra学习记录

#include <iostream>
#include <fstream>
#define MAX 50
#define INFINITY 114514 //此数为正无穷大，可以随便设置，如32767等等
using namespace std;
ofstream out("H:/vscode/out.txt");
ifstream in("H:/vscode/in.txt");
int dist[MAX];  //原点到下标对应的顶点距离
int path[MAX];  //经过的路径
int collected[MAX]; //访问过的结点
typedef struct Arc
{
    int adjvex;
    Arc *next;
    int wei;
} Arc;
struct Vertex
{
    string name;
    Arc *firstarc;
};
struct Graph
{
    int Arcnum;
    int Vertexnum;
    Vertex list[MAX];
};
Graph *CreateGraph(int Vn, int An) //Vn 顶点数 ,An 边数
{
    Graph *G = new Graph;
    G->Vertexnum = Vn;
    G->Arcnum = An;
    for (int k = 1; k <= Vn; k++)
    {
        in >> G->list[k].name;
        G->list[k].firstarc = NULL;
    }
    return G;
}
void InsertArc(Graph *&G, int V1, int V2, int weight)
{
    Arc *p = new Arc;
    p->adjvex = V2;
    p->wei = weight;
    p->next = G->list[V1].firstarc;
    G->list[V1].firstarc = p;
}
void outputGraph(Graph *G)
{
    for (int i = 1; i <= G->Vertexnum; i++)
    {
        Arc *p;
        out << G->list[i].name << ": ";
        for (p = G->list[i].firstarc; p; p = p->next)
        {
            out << "(" << G->list[p->adjvex].name << "," << p->wei << ") ";
        }
        out << endl;
    }
}
void buildPath(Graph *&G)
{
    int V1, V2, weight;
    for (int i = 1; i <= G->Arcnum; i++)
    {
        in >> V1 >> V2 >> weight;
        InsertArc(G, V1, V2, weight);
    }
}
int FindMinDist(Graph *G, int dist[], int collected[])
{ /* 返回未被收录顶点中dist最小者 */
    int MinV, V;
    int MinDist = INFINITY;

    for (V = 1; V <= G->Vertexnum; V++)
    {
        if (collected[V] == false && dist[V] < MinDist)
        {
            /* 若V未被收录，且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距离 */
            MinV = V;          /* 更新对应顶点 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV;        /* 返回对应的顶点下标 */
    else
        return -1; /* 若这样的顶点不存在，返回错误标记 */
}
void Dijkstra(Graph *G, int v) //v为原点
{
    struct Stack
    {
        int top = -1;
        int data[MAX];
    };
    for (int i = 1; i <= G->Vertexnum; i++)
    {
        path[i] = -1;
        dist[i] = INFINITY;
        collected[i] = 0;
    }
    Arc *p;
    int w;
    dist[v] = 0;
    collected[v] = 1;
    for (p = G->list[v].firstarc; p; p = p->next)
    {
        dist[p->adjvex] = p->wei;
        if (dist[p->adjvex] < INFINITY)
            path[p->adjvex] = v;
    }
    while (1)
    {
        w = FindMinDist(G, dist, collected);
        if (w == -1)
            break;
        collected[w] = 1;
        for (p = G->list[w].firstarc; p; p = p->next)
        {
            if (collected[p->adjvex] == 0 && p->wei < INFINITY)
            {
                if (dist[w] + p->wei < dist[p->adjvex])
                {
                    dist[p->adjvex] = dist[w] + p->wei;
                    path[p->adjvex] = w;
                }
            }
        }
    }

    for (int i = 1; i <= G->Vertexnum; i++)//输出从原点到所有点的最短路径
    {
        Stack sq;

        out <<"from "<<G->list[v].name << " to " << G->list[i].name << " need " << dist[i] << endl;
        int j = i;
        sq.data[++sq.top] = j;
        while (j != -1)
        {
            sq.data[++sq.top] = path[j];
            j = path[j];
        }
        while (sq.top != -1)
        {
            out << G->list[sq.data[--sq.top]].name << " ";
        }
        out << endl;
    }
}
int main()
{
    int Vn, An; //定点数和边数
    in >> Vn >> An;
    Graph *G = CreateGraph(Vn, An);
    buildPath(G);
    outputGraph(G);
    Dijkstra(G, 3);//假设从原点为3，开始
    system("pause");
}