【作业存档】Dijkstra算法的练习

作为一个无脑莽撞的少年，完成这次（超简单的）作业历经波折。

目标是用函数实现，找到图中每个点到源所有的加权最短路径，记录下总长度（边的权值和）和条数。如果不相连，总长度为-1和条数0

dist记录总长度，count记录找到了几条这样的路径。

用Dijkstra算法可以直接实现非常简单，但是我太心急和浮躁，没有彻底弄清楚D算法就直接上手，导致绕了远路。

不过，也学到了很重要的东西：

1.写代码前一定要搞清楚算法，

2.学习数据结构不能听听课就好，课下要花功夫钻研。

3.发现自己的算法改起来很困难的时候，直接推翻换一个思路。

4.写同一个代码超过两个小时就去做点别的事情，回来可以直接推翻重写。

【知识点复习】：用矩阵表示有向图，行代表出发的结点，列代表进入的节点

【错误总结】：

如果要用Queue来实现Dijkstra算法，需要用最小堆才可以（（（非常麻烦所以在数据量很小的时候就用数组储存吧

用两次D算法（参考网上代码，后来发现可以合并成一次）和用一次D算法中有很多细节错误（if语句括号没括全），但最重要的问题是，缺少Graph->G[V][W]!= INFINITY

然而题目并没有说过这种事情（（

下面放上最后的代码

void ShortestDist(MGraph Graph, int dist[], int count[], Vertex S){ bool isVisit[MaxVertexNum]; int i, minDis,V, W, tmpDis; for (i = 0; i < Graph->Nv; i++){ dist[i] = -1; count[i] = 0; isVisit[i] = false; } dist[S] = 0; count[S] = 1; while (1){ minDis = INFINITY; for (i = 0; i < Graph->Nv; i++){ if (!isVisit[i] && dist[i] < minDis && dist[i] != -1){ V = i; minDis = dist[V]; } } if (minDis == INFINITY) break; isVisit[V] = true; for (W = 0; W < Graph->Nv; W++){ tmpDis = dist[V] + Graph->G[V][W]; if(isVisit[W] == false && Graph->G[V][W] >= 0 && Graph->G[V][W] != INFINITY){ if( (dist[V] + Graph->G[V][W] < dist[W]||dist[W] == -1)){ dist[W] = tmpDis; count[W] = count[V]; } else if (dist[V] + Graph->G[V][W] == dist[W]){ count[W] += count[V]; } } } } } 下面为题目

4-1 Shortest Path [3]   (25分)

Write a program to not only find the weighted shortest distances, but also count the number of different minimum paths from any vertex to a given source vertex in a digraph. It is guaranteed that all the weights are positive.

Format of functions:

void ShortestDist( MGraph Graph, int dist[], int count[], Vertex S );

where MGraph is defined as the following:

typedef struct GNode *PtrToGNode; struct GNode{ int Nv; int Ne; WeightType G[MaxVertexNum][MaxVertexNum]; }; typedef PtrToGNode MGraph;

The shortest distance from V to the source S is supposed to be stored in dist[V]. If V cannot be reached from S, store -1 instead. The number of different minimum paths from V to the source S is supposed to be stored in count[V] and count[S]=1.

Sample program of judge:

#include <stdio.h> #include <stdlib.h> typedef enum {false, true} bool; #define INFINITY 1000000 #define MaxVertexNum 10 /* maximum number of vertices */ typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */ typedef int WeightType; typedef struct GNode *PtrToGNode; struct GNode{ int Nv; int Ne; WeightType G[MaxVertexNum][MaxVertexNum]; }; typedef PtrToGNode MGraph; MGraph ReadG(); /* details omitted */ void ShortestDist( MGraph Graph, int dist[], int count[], Vertex S ); int main() { int dist[MaxVertexNum], count[MaxVertexNum]; Vertex S, V; MGraph G = ReadG(); scanf("%d", &S); ShortestDist( G, dist, count, S ); for ( V=0; V<G->Nv; V++ ) printf("%d ", dist[V]); printf("\n"); for ( V=0; V<G->Nv; V++ ) printf("%d ", count[V]); printf("\n"); return 0; } /* Your function will be put here */

Sample Input (for the graph shown in the figure):

8 11 0 4 5 0 7 10 1 7 30 3 0 40 3 1 20 3 2 100 3 7 70 4 7 5 6 2 1 7 5 3 7 2 50 3

Sample Output:

40 20 100 0 45 53 -1 50 1 1 4 1 1 3 0 3