Dijkstra算法 数据结构 浙江大学 陈越、何钦铭

Dijkstra算法 数据结构 浙江大学 陈越、何钦铭

算法主体就是老师给的，自己把它写完，能跑起来。能在visual studio 2022上跑起来。

#include 
#include 
#include 
#include 
#include 
#include 

typedef  int Distance;
//这个结构没什么通用性，它的int是从起始点到该顶点的距离，它的int*是指向dist[]的指针。
struct Distance_P
{
    Distance d;
    Distance* p;
};


typedef struct HNode* Heap; 
typedef struct Distance_P ElementType;
struct HNode {
    ElementType* Data; 
    int Size;          
    int Capacity;      
};
typedef Heap MaxHeap; 
typedef Heap MinHeap; 

MinHeap Create_Min_Heap(int MaxSize)
{ 

    MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
    H->Data = (ElementType*)malloc((MaxSize + 1) * sizeof(ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    ElementType temp_e = { INT_MIN,NULL };
    H->Data[0] =temp_e ; 
    // 我 我为这个 *** 作重载了=
    return H;
}
bool IsFull(MinHeap H)
{
    return (H->Size == H->Capacity);
}
bool IsEmpty(MinHeap H) {
    //这个 *** 作不管没有create的bug;
    return (H->Size ==0);
}
bool Insert(MinHeap H, Distance d,Distance* p)
{ 
    ElementType X = { d,p };
    int i;
    if (IsFull(H)) {
        printf("最小堆已满");
        return false;
    }
    i = ++H->Size; 
    for (; H->Data[i / 2].d > X.d; i /= 2)
        H->Data[i] = H->Data[i / 2]; 
    H->Data[i] = X; 
    return true;
}
ElementType DelRoot(MinHeap H)
{
    //这个 *** 作不管没有第0项的bug;
    if (IsEmpty(H)) { 
        printf("MinHeap is Emptyn");
        return H->Data[0]; }
    ElementType anwser = H->Data[1];
    
    ElementType X = H->Data[H->Size--]; 
    int Parent , Child;
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Data[Child].d > H->Data[Child + 1].d))
            Child++;  
        if (X.d <= H->Data[Child].d) break; 
        else  
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;

    return anwser;
}
MinHeap  test_Heap()
{
    int MaxSize;
    scanf_s("%d", &MaxSize);    
    MinHeap H = Create_Min_Heap(MaxSize);
    //试验次数请不要超过100次;
    int dist[100];
    int* p = dist;


    while (1)
    {
        int a;
        scanf_s("%d", &a);
        if (a == 0) break;
        if (a > 0) {
            Insert(H, a, p);
            ++p;
        }
        else
        {
            if (-a > H->Size) a = H->Size;
            else a = -a;

            for (int i = 0; i != a; ++i)
            {
                ElementType temp = DelRoot(H);
                printf("%d  %pn", temp.d,temp.p);
            }
        }
    }
    return H;

}




//用邻接表存储 you权有向图。
//所以要复习一遍邻接表的构造。
//如果你要用到邻接表，你又会发现，你好像只能用动态内存来存 出 或 入 的数组。
// 我的邻接链表是出度和入度都有的。
//当你要表示有权图的时候，是不是要把权重写道listnode里面呢？有没有别的办法？
//这样权重被存储了两次。出一次，入一次。

struct ListNode
{
    int vertex;
    int weight;
    struct ListNode* next;
};
struct Adjacency_List {
    int vertex_N;
    struct ListNode** point_me;
    struct ListNode** point_other;
};
typedef int Vertex;
struct Adjacency_List* set_vertex_N(struct Adjacency_List* pa, int n)
{
    //无检查，默认你输入的全部正确;
    //你可以检查一下，whether pa所指向的Adjacency_List had been initialized or whether n more than 0;
    //I just ignore it.
    //这个函数就是分配两个数组，数组里存指针，指针是链表头，
    pa->vertex_N = n;
    pa->point_me = malloc(sizeof(struct ListNode*) * n);
    pa->point_other = malloc(sizeof(struct ListNode*) * n);

    //因为是初始化，所以，我要清理一下，让上述数组的每个元素都是NULL
    for (int i = 0; i != n; ++i)
    {
        pa->point_me[i] = NULL;
        pa->point_other[i] = NULL;
    }
    return pa;
}
struct Adjacency_List* insert_edge(struct Adjacency_List* const pa, int vertex1, int vertex2,int weight) {
    //vertex1----> vertex2
    struct ListNode* temp =(struct ListNode*) malloc(sizeof(struct ListNode));
    temp->vertex = vertex1;
    temp->next = pa->point_me[vertex2];
    temp->weight = weight;
    pa->point_me[vertex2] = temp;

    temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->vertex = vertex2;
    temp->next = pa->point_other[vertex1];
    temp->weight = weight;
    pa->point_other[vertex1] = temp;
    return pa;
}
void build_graph(struct Adjacency_List* pa)
{
    int vertexN;
    puts("没有审查bug，请保证输入正确的图。");
    puts("输入顶点数");
    scanf_s("%d", &vertexN);
    set_vertex_N(pa, vertexN);
    puts("输入vertex1----> vertex2,  权重；输入三个负数，则结束图的创建：");
    int vertex1, vertex2,weight;
    scanf_s("%d %d %d", &vertex1, &vertex2,&weight);
    while (vertex1 >= 0) {
        insert_edge(pa, vertex1, vertex2,weight);
        scanf_s("%d %d %d", &vertex1, &vertex2, &weight);
    }
}
//Dijkstra算法
//1先初始化一个距离数组，起点的为零，起点出去的点就其边长，剩下的其它点的距离为无穷的
//2挑出最小的边长，把它（B）加进来。然后审查谁（B的邻接点）的距离变小了，改变它的距离。
// 重复步骤2直至结束。


struct TwoIntP {
    
    int* p1;
    int  size1;
    int* p2;
    int  size2;
};


bool Dijkstra(struct Adjacency_List* Graph, int dist[], int path[], Vertex S)
{
    bool* collected=(bool*)malloc(sizeof(bool)*(Graph->vertex_N));
    MinHeap H = Create_Min_Heap(Graph->vertex_N);//这个最小堆理论上得建多大规模呢？
        
    for (Vertex V = 0; V < Graph->vertex_N; ++V) {
        dist[V] = INT_MAX;
        collected[V] = false;
        path[V] = -1;
    }
    struct ListNode* ln = Graph->point_other[S];
    while (ln != NULL)
    {
        dist[ln->vertex] = ln->weight;
        Insert(H, ln->weight, &dist[ln->vertex]);//起点的出邻接点都插入了堆中，起点没有插入堆中，其它点也没有
        path[ln->vertex] = S; //看到某个点就必须把它的上步路径加入，但是，不直接收录
        //它。 所以这里不能collected；
        ln = ln->next;
    }
    
    dist[S] = 0;
    collected[S] = true;

    while (true)
    {
        ElementType E = DelRoot(H);
        if (E.p == NULL) break;
        if (E.d > *(E.p))
        {
            Insert(H, *(E.p), E.p);
            continue;
        }
        Vertex V = E.p - dist;//不该不该，当初的ElementType中的指针应该定义为
        //dist中的序号来着。
        if (collected[V] == true) continue;

         collected[V] = true;
         ln = Graph->point_other[V];
         while (ln != NULL)
         {
             if (ln->weight < 0) {
                 printf("Dijkstra can not deal a Graph with 负数n");
                 return false;
             }
             if ( collected[ln->vertex] == false && 
                 dist[V] + ln->weight < dist[ln->vertex])
             {
                 dist[ln->vertex] = dist[V] + ln->weight;
                 Insert(H, dist[ln->vertex], &dist[ln->vertex]);
                 path[ln->vertex] = V;
             }
             ln = ln->next;
         }
    }

    return true;
}

bool test_Dijkstra(struct Adjacency_List* Graph,struct TwoIntP* T)
{
    Vertex start;
    printf("输入起点：n");
    scanf_s("%d", &start);
    int* dist = (int*)malloc(sizeof(int) * Graph->vertex_N);
    int* path = (int*)malloc(sizeof(int) * Graph->vertex_N);
    
  bool a= Dijkstra(Graph, dist, path, start);

  T->size1 = Graph->vertex_N;
  T->size2 = Graph->vertex_N;
  T->p1 = dist;
  T->p2 = path;
  return a;
}

void show_distance_or_path(int d[], int n) {
    for (int i = 0; i < n; ++i) {
        printf("%d  ", d[i]);
    }
    printf("n");
}

int main() {
    //我想
   // MinHeap H = test_Heap();

    struct Adjacency_List al;
    build_graph(&al);
    struct TwoIntP ti2;
    test_Dijkstra(&al, &ti2);
    show_distance_or_path(ti2.p1, ti2.size1);
    printf("n");

    show_distance_or_path(ti2.p2, ti2.size2);
    printf("n");

    return 0;
}