DS5

Problem A.a

Find the shortest path from A to all other vertices for the graph in Figure 9.80.

通过邻接矩阵定义加权图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//index-char array
    char id[7] = {'A', 'B', 'C', 'D', 'E', 'F', 'G',};
    //generate the graph
    int G[7][7];
    //init = 0
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            G[i][j] = INF;
        }
    }
    //add edge
    G[0][1] = 5;
    G[0][2] = 3;
    G[1][2] = 2;
    G[1][4] = 3;
    G[1][6] = 1;
    G[2][3] = 7;
    G[2][4] = 7;
    G[3][0] = 2;
    G[3][5] = 6;
    G[4][3] = 2;
    G[4][5] = 1;
    G[6][4] = 1;

创建Dijkstra算法所需表

  • vertex 表示目标（终点）顶点，对应关系参照表id[7] ，初始化为0~6
  • ischecked 记录该顶点是否访问，访问后标记为1，初始化为0
  • length 记录当前最短距离，初始化为INF
  • Path为链表，记录最短距离路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//shortest path by Dijkstra
    int vertex[7];
    int ischecked[7];
    int length[7];
    PTNode Path[7];
    //init array
    for (int i = 0; i < 7; i++) {
        vertex[i] = i;
        ischecked[i] = 0;
        length[i] = INF;
        Path[i] = (PTNode) malloc(sizeof(struct pathnode));
        Path[i]->vertex = id[i];
        Path[i]->next = NULL;
    }

Dijkstra基本步

对于起始顶点：

  • 标记：ischecked[0] = 1
  • 计算（更新）距离：length[0] = 0
  • 找出相邻的、未标记的（未访问过）、最近的顶点作为下一轮起始顶点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//start from vertex 0(A)
ischecked[0] = 1;
length[0] = 0;

for (int i = 0; i < 7; i++) {
    if (G[0][i] != INF) {
        length[i] = G[0][i];
        addvertex(&Path[i], id[0]);
    }
}
//find the shortest vertex
int minpathval = INF;
int minpathindex = -1;
for (int i = 0; i < 7; i++) {
    if (ischecked[i] == 0 && length[i] < minpathval) {
        minpathval = length[i];
        minpathindex = i;
    }
}

Dijkstra推导步

由上步知，minpathindex将作为新一轮起始顶点

1
2
//update the length array
int newvertex = minpathindex;

引入newvertex != -1作为循环结束的标志：当所有顶点均被标记后，算法结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while (newvertex != -1) {
    ischecked[newvertex] = 1;
    for (int i = 0; i < 7; i++) {
        if (ischecked[i] == 0 && G[newvertex][i] != INF) {
            int newpathlen = length[newvertex] + G[newvertex][i];
            if (length[i] > newpathlen) {
                length[i] = newpathlen;
                //update the path
                copypath(Path[newvertex], Path[i]);
                addvertex(&Path[i], id[newvertex]);
            }
        }
    }
    //find the shortest vertex
    minpathval = INF;
    newvertex = -1;
    for (int i = 0; i < 7; i++) {
        if (ischecked[i] == 0 && length[i] < minpathval) {
            minpathval = length[i];
            newvertex = i;
        }
    }
}

输出（对于该样例）

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
The shortest path from A to other vertex is:
A->A::
PATH: A
length: 0
-----
A->B::
PATH: A->B
length: 5
-----
A->C::
PATH: A->C
length: 3
-----
A->D::
PATH: A->B->G->E->D
length: 9
-----
A->E::
PATH: A->B->G->E
length: 7
-----
A->F::
PATH: A->B->G->E->F
length: 8
-----
A->G::
PATH: A->B->G
length: 6
-----

完整代码

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
#include <stdio.h>
#include <stdlib.h>

#define INF 10e6
typedef struct pathnode *PTNode;
struct pathnode {
    char vertex;
    PTNode next;
};

void addvertex(PTNode *head, char vertex) {
    PTNode newnode = (PTNode) malloc(sizeof(struct pathnode));
    newnode->vertex = vertex;
    newnode->next = NULL;
    if (*head == NULL) {
        *head = newnode;
    }
    else {
        PTNode p = *head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = newnode;
    }
}

void copypath(PTNode src, PTNode dest) {
    src = src->next;
    dest->next = NULL;
    while (src != NULL) {
        addvertex(&dest, src->vertex);
        src = src->next;
    }
}
int main() {
    //index-char array
    char id[7] = {'A', 'B', 'C', 'D', 'E', 'F', 'G',};
    //generate the graph
    int G[7][7];
    //init = 0
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            G[i][j] = INF;
        }
    }
    //add edge
    G[0][1] = 5;
    G[0][2] = 3;
    G[1][2] = 2;
    G[1][4] = 3;
    G[1][6] = 1;
    G[2][3] = 7;
    G[2][4] = 7;
    G[3][0] = 2;
    G[3][5] = 6;
    G[4][3] = 2;
    G[4][5] = 1;
    G[6][4] = 1;


    //shortest path by Dijkstra
    int vertex[7];
    int ischecked[7];
    int length[7];
    PTNode Path[7];
    //init array
    for (int i = 0; i < 7; i++) {
        vertex[i] = i;
        ischecked[i] = 0;
        length[i] = INF;
        Path[i] = (PTNode) malloc(sizeof(struct pathnode));
        Path[i]->vertex = id[i];
        Path[i]->next = NULL;
    }

    //start from vertex 0(A)
    ischecked[0] = 1;
    length[0] = 0;

    for (int i = 0; i < 7; i++) {
        if (G[0][i] != INF) {
            length[i] = G[0][i];
            addvertex(&Path[i], id[0]);
        }
    }
    //find the shortest vertex
    int minpathval = INF;
    int minpathindex = -1;
    for (int i = 0; i < 7; i++) {
        if (ischecked[i] == 0 && length[i] < minpathval) {
            minpathval = length[i];
            minpathindex = i;
        }
    }
    //update the length array
    int newvertex = minpathindex;
    while (newvertex != -1) {
        ischecked[newvertex] = 1;
        for (int i = 0; i < 7; i++) {
            if (ischecked[i] == 0 && G[newvertex][i] != INF) {
                int newpathlen = length[newvertex] + G[newvertex][i];
                if (length[i] > newpathlen) {
                    length[i] = newpathlen;
                    //update the path
                    copypath(Path[newvertex], Path[i]);
                    addvertex(&Path[i], id[newvertex]);
                }
            }
        }
        //find the shortest vertex
        minpathval = INF;
        newvertex = -1;
        for (int i = 0; i < 7; i++) {
            if (ischecked[i] == 0 && length[i] < minpathval) {
                minpathval = length[i];
                newvertex = i;
            }
        }
    }

    printf("The shortest path from A to other vertex is:\n");
    for (int i = 0; i < 7; i++) {
        printf("A->%c::\n", id[i]);
        PTNode p = Path[i]->next;
        printf("PATH: ");
        while (p != NULL) {
            printf("%c->", p->vertex);
            p = p->next;
        }
        printf("%c", id[i]);
        printf("\n");
        printf("length: %d\n-----\n", length[i]);
    }
    return 0;
}

Problem A.b

Find the shortest unweighted path from B to all other vertices for the graph in Figure 9.80.

修改加权图为无权图

1
2
3
4
5
6
7
8
9
10
11
12
13
//add edge
G[0][1] = 1;
G[0][2] = 1;
G[1][2] = 1;
G[1][4] = 1;
G[1][6] = 1;
G[2][3] = 1;
G[2][4] = 1;
G[3][0] = 1;
G[3][5] = 1;
G[4][3] = 1;
G[4][5] = 1;
G[6][4] = 1;

起点更改为1（B）

1
2
3
4
5
6
7
8
9
10
//start from vertex 1(B)
ischecked[1] = 1;
length[1] = 0;

for (int i = 0; i < 7; i++) {
    if (G[1][i] != INF) {
        length[i] = G[1][i];
        addvertex(&Path[i], id[1]);
    }
}

输出（对于该样例）

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
The shortest path from B to other vertex is:
B->A::
PATH: B->C->D->A
length: 3
-----
B->B::
PATH: B
length: 0
-----
B->C::
PATH: B->C
length: 1
-----
B->D::
PATH: B->C->D
length: 2
-----
B->E::
PATH: B->E
length: 1
-----
B->F::
PATH: B->E->F
length: 2
-----
B->G::
PATH: B->G
length: 1
-----

完整代码

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
#include <stdio.h>
#include <stdlib.h>

#define INF 10e6
typedef struct pathnode *PTNode;
struct pathnode {
    char vertex;
    PTNode next;
};

void addvertex(PTNode *head, char vertex) {
    PTNode newnode = (PTNode) malloc(sizeof(struct pathnode));
    newnode->vertex = vertex;
    newnode->next = NULL;
    if (*head == NULL) {
        *head = newnode;
    }
    else {
        PTNode p = *head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = newnode;
    }
}

void copypath(PTNode src, PTNode dest) {
    src = src->next;
    dest->next = NULL;
    while (src != NULL) {
        addvertex(&dest, src->vertex);
        src = src->next;
    }
}

int main() {
    //index-char array
    char id[7] = {'A', 'B', 'C', 'D', 'E', 'F', 'G',};
    //generate the graph
    int G[7][7];
    //init = 0
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            G[i][j] = INF;
        }
    }
    //add edge
    G[0][1] = 1;
    G[0][2] = 1;
    G[1][2] = 1;
    G[1][4] = 1;
    G[1][6] = 1;
    G[2][3] = 1;
    G[2][4] = 1;
    G[3][0] = 1;
    G[3][5] = 1;
    G[4][3] = 1;
    G[4][5] = 1;
    G[6][4] = 1;


    //shortest path by Dijkstra
    int vertex[7];
    int ischecked[7];
    int length[7];
    PTNode Path[7];
    //init array
    for (int i = 0; i < 7; i++) {
        vertex[i] = i;
        ischecked[i] = 0;
        length[i] = INF;
        Path[i] = (PTNode) malloc(sizeof(struct pathnode));
        Path[i]->vertex = id[i];
        Path[i]->next = NULL;
    }

    //start from vertex 1(B)
    ischecked[1] = 1;
    length[1] = 0;

    for (int i = 0; i < 7; i++) {
        if (G[1][i] != INF) {
            length[i] = G[1][i];
            addvertex(&Path[i], id[1]);
        }
    }
    //find the shortest vertex
    int minpathval = INF;
    int minpathindex = -1;
    for (int i = 0; i < 7; i++) {
        if (ischecked[i] == 0 && length[i] < minpathval) {
            minpathval = length[i];
            minpathindex = i;
        }
    }
    //update the length array
    int newvertex = minpathindex;
    while (newvertex != -1) {
        ischecked[newvertex] = 1;
        for (int i = 0; i < 7; i++) {
            if (ischecked[i] == 0 && G[newvertex][i] != INF) {
                int newpathlen = length[newvertex] + G[newvertex][i];
                if (length[i] > newpathlen) {
                    length[i] = newpathlen;
                    //update the path
                    copypath(Path[newvertex], Path[i]);
                    addvertex(&Path[i], id[newvertex]);
                }
            }
        }
        //find the shortest vertex
        minpathval = INF;
        newvertex = -1;
        for (int i = 0; i < 7; i++) {
            if (ischecked[i] == 0 && length[i] < minpathval) {
                minpathval = length[i];
                newvertex = i;
            }
        }
    }

    printf("The shortest path from B to other vertex is:\n");
    for (int i = 0; i < 7; i++) {
        printf("B->%c::\n", id[i]);
        PTNode p = Path[i]->next;
        printf("PATH: ");
        while (p != NULL) {
            printf("%c->", p->vertex);
            p = p->next;
        }
        printf("%c", id[i]);
        printf("\n");
        printf("length: %d\n-----\n", length[i]);
    }
    return 0;
}

Problem B.a

Explain how to modify Dijkstra’s algorithm to produce a count of the number of different minimum paths from v to w.

对每个顶点构建一个前缀表（原算法是直接更改），结束后统计权重和，以前缀表向前排查出整条路径。

Problem B.b

Explain how to modify Dijkstra’s algorithm so that if there is more than one minimum path from v to w, a path with the fewest number of edges is chosen.

依照B.a，不难比较不同最短路径的边数

Problem C.a

Find a minimum spanning tree for the graph in Figure 9.82 using both Prim’s and Kruskal’s algorithms.

Prim 算法

  1. 以任意顶点为起始点（以0为例）
  2. 将顶点加入集合
  3. 查找与集合相连、不在集合内、最近顶点
  4. 将顶点加入集合
  5. 重复直至全部顶点入集

代码

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
void MinSpanTree_Prim(Graph G) {
    int min, i, j, k;
    int adjvex[n_vertex];
    int lowcost[n_vertex];
    lowcost[0] = 0;
    adjvex[0] = 0;
    for (i = 1; i < n_vertex; i++) {
        lowcost[i] = G[0][i];
        adjvex[i] = 0;
    }
    for (i = 1; i < n_vertex; i++) {
        min = INF;
        j = 1;
        k = 0;
        while (j < n_vertex) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        printf("(%d,%d)", adjvex[k], k);
        lowcost[k] = 0;
        for (j = 1; j < n_vertex; j++) {
            if (lowcost[j] != 0 && G[k][j] < lowcost[j]) {
                lowcost[j] = G[k][j];
                adjvex[j] = k;
            }
        }
    }
}

kruskal 算法

  1. 查找最小的边，将最小边的两个顶点合并同一集合，该边作为最小树的边
  2. 查找次小边，次小边两顶点不属于同一集合，合并两集，该边作为最小树的边
  3. 查找次小边，次小边两顶点属于同一集合，该边不作为最小树的边
  4. 重复，直至所有顶点入集

代码

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
void MinSpanTree_Kruskal(Graph G) {
    int i, j, n, m;
    Edge edges;
    int parent[n_vertex];
    for (i = 0; i < n_vertex; i++) {
        parent[i] = 0;
    }
    edges = (Edge) malloc(sizeof(struct ENode));
    edges->Next = NULL;
    for (i = 0; i < n_vertex; i++) {
        for (j = i + 1; j < n_vertex; j++) {
            if (G[i][j] < INF) {
                InsertEdge(edges, i, j, G[i][j]);
            }
        }
    }
    edges = edges->Next;
    while (edges != NULL) {
        n = Find(parent, edges->V1);
        m = Find(parent, edges->V2);
        if (n != m) {
            parent[n] = m;
            printf("(%d,%d)", edges->V1, edges->V2);
        }
        edges = edges->Next;
    }
}

其中对Edge定义如下，

1
2
3
4
5
typedef struct edge {
    int begin;
    int end;
    int weight;
}Edge;

Problem C.b

Is this minimum spanning tree unique? Why?

不唯一，当图中存在权值相同时，依据初始选择位置不同，优先构建的最小树不同，导致生成的最小树不同