无权最短路径_unweighted shortest path

作者：AllinToyou | 2024-02-27 10:33:09

踩

unweighted shortest path

【0】README

0.1） 本文总结于数据结构与算法分析，源代码均为原创，旨在理解 无权最短路径 的思想并用源代码加以实现；

【1】无权最短路径相关概念（边的权值赋值为1）

1.1）概述：下图就是表示一个无权图G。使用某个顶点s作为输入参数，我们想要计算从s到所有其他顶点的最短路径；
这里写图片描述
1.2）0路径：若我们选择s 为 v3，此时立刻可以说出从s 到v3的最短路径是0路径；
1.3）算法描述：

step1）寻找所有与s 距离为 1 的顶点，此时我们看到 v1和v6 与s只有一边之遥；
step2）寻找所有与s 距离为 2 的顶点，即找出所有邻接到 v1 和 v6的顶点（与v1和v6 距离为1的顶点），得到v2和v4，所以v1到v2或者v4的距离为2；
……
step3）循环这个过程，直到所有的顶点都被遍历到；

Conclusion）以上搜索过程称为广度优先搜索
广度优先搜索）该方法按层处理顶点： 距开始点最近的那些顶点首先被赋值，而最远的那些顶点最后被赋值，这很像对树的层次遍历；

【2】如何实现上述算法？

2.1）对于每个顶点，我们将跟踪三个信息（info）：

I1）dv栏(distance)：我们把从s开始到顶点的距离放到 dv栏中，开始的时候，除开s所有的顶点都是不可达到的，而s的路径长为0；
I2）pv栏(path)： pv栏中的项为薄记变量，它将使我们能够显示出实际的路径；
I3）known栏： Known中的项点被处理后置为1；

2.2）开始，所有的顶点都不是 Known，包括开始顶点。当一个顶点被标记为已知是，我们就确信不会再找到更便宜的路径，因此对该顶点的处理实质上已经完成了；

【3】我们使用类似于拓扑排序的做法来提供寻找无权最短路径算法的性能

3.1）算法描述：在任一时刻，只存在两种类型的未知顶点，他们的dv≠∞，一些顶点的dv=CurrDist，而其余的则有 dv=CurrDist+1；
3.2）使用队列把这种想法进一步精化： 在迭代开始的时候，队列只含有距离为CurrDist的那些顶点。当我们添加距离为 CurrDist+1的那些邻接顶点时，由于它们自队尾入队，因此这就保证了它们直到所有距离为 CurrDist 的顶点都被处理后才被处理。在距离为 CurrDist处的最后一个顶点出队并被处理之后，队列只含有距离为 CurrDist+1的顶点，因此该过程将不断进行下去。我们只需要把开始的节点放入队列中以启动这个过程即可；
3.3）时间复杂度： 只要使用邻接表，则运行时间就是 O（|E| + |V|）；
3.4）无权最短路径算法实例图如下：
（显然，某顶点出队后，更新其相应的known为1；再查找出队顶点vertex的邻接顶点，如果有的话，将他们依次入队，依次更新distance自增1且path路径更新为出队顶点vertex的顶点编号）

【4】source code + printing results

4.1）download source code：
https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter9/p224_unweighted_shortest_path
4.2）source code at a glance (for full code, please download source code following the given link above)：

#include "unweightedTable.h"

// allocate the memory for every element in unweighted table  
UnweightedTable makeEmptyUnweightedTable()
{
    UnweightedTable element;

    element = (UnweightedTable)malloc(sizeof(struct UnweightedTable));
    if(!element)
    {
        Error("out of space ,from func makeEmptyUnweightedTable");
        return NULL;
    }   
    element->known = 0; // 1 refers to accessed , also 0 refers to not accessed
    element->distance = MaxInt;
    element->path = -1; // index starts from 0

    return element;
}

//allocate the memory for initializing unweighted table
UnweightedTable *initUnweightedTable(int size)
{   
    UnweightedTable* table;
    int i;

    table = (UnweightedTable*)malloc(sizeof(UnweightedTable) * size);
    if(!table)
    {
        Error("out of space ,from func initUnweightedTable");
        return NULL;
    }

    for(i = 0; i < size; i++)
    {
        table[i] = makeEmptyUnweightedTable();      
        if(!table[i])
            return NULL;
    }

    return table;
} 

//computing the unweighted shortest path between the vertex under initIndex and other vertexs
void unweighted_shortest_path(AdjTable* adj, int size, int startVertex, Queue queue)
{       
    int adjVertex;  
    UnweightedTable* table;
    ElementType vertex;     
    AdjTable temp; 

    table = initUnweightedTable(size);   

    enQueue(queue, startVertex-1); //if let start vertex equals to v3, then initIndex=3 and let index=2 enter the queue     
    table[startVertex-1]->distance = 0;// update the distance 
    table[startVertex-1]->path = 0;// update the path of starting vertex

    while(!isEmpty(queue))
    {
        vertex = deQueue(queue); // if the queue is not empty, conducting departing queue   
        table[vertex]->known = 1; // update the vertex as accessed, also responding known 1

        temp = adj[vertex]->next;
        while(temp)
        {
            adjVertex = temp->index; // let each adjVertex adjacent to vertex enter the queue
            if(table[adjVertex]->path == -1) // key that judge whether corresponding element's path equals to -1 ,-1 means the element has never entered the queue
            {
                enQueue(queue, adjVertex); 
                table[adjVertex]->distance = table[vertex]->distance + 1;// update the distance 
                table[adjVertex]->path = vertex; //update the path of adjVertex, also responding path evaluated as vertex
            }
            temp = temp->next;      
        }                                       
    }

    disposeQueue(queue);
    //print unweighted table
    printUnweightedtable(table, size, startVertex);

    printf("\n\t");
} 

//print unweighted table
void printUnweightedtable(UnweightedTable* table, int size, int startVertex)
{
    int i;
    int path;
    char *str[4] = 
    {
        "vertex",
        "known",
        "distance",
        "path"
    };

    printf("\n\t unweighted shortest path table are as follows:\n");    
    printf("\n\t %6s%6s%9s%5s", str[0], str[1], str[2], str[3]);    
    for(i=0; i<size; i++)
    {       
        if(i != startVertex-1)              
            printf("\n\t %-3d   %3d   %5d      v%-3d  ", i+1, table[i]->known, table[i]->distance, table[i]->path+1);
        else
            printf("\n\t *%-3d  %3d   %5d      %-3d  ", i+1, table[i]->known, table[i]->distance, 0);
    }    
}

int main()
{ 
    AdjTable* adj;      
    Queue queue;
    int size = 7;
    int i;
    int j;
    int column = 4;
    int startVertex;

    int adjTable[7][4] = 
    {
        {2, 4, 0, 0},
        {4, 5, 0, 0},
        {1, 6, 0, 0},
        {3, 5, 6, 7},
        {7, 0, 0, 0},
        {0, 0, 0, 0},
        {6, 0, 0, 0}
    };

    printf("\n\n\t ====== test for topological sorting with adjoining table ======\n");
    adj = initAdjTable(size);   
    queue = initQueue(size);

    printf("\n\n\t ====== the initial adjoining table is as follows:======\n");
    for(i = 0; i < size; i++)
        for(j = 0; j < column; j++) 
            if(adjTable[i][j])          
                insertAdj(adj, adjTable[i][j]-1, i); // insertAdj the adjoining table over                           

    printAdjTable(adj, size);

    // finding the unweighted shortest path starts  
    // void unweighted_shortest_path(AdjTable* adj, int size, int initIndex, Queue queue)
    startVertex = 3; // we set the vertex3 as the start vertex (but you know, whose index in array is 2)
    unweighted_shortest_path(adj, size, startVertex, queue);

    return 0;
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

4.3）printing results：
这里写图片描述