这个很早就写了,先把源代码发上来了,其他内容择日补充。
一、最短路径算法
例子:
二、源代码
- /******************************
-
* date:2011-3-31
-
* filename:dijkstra_main.c
-
* by:Jelline
-
* ****************************/
-
-
#include <stdio.h>
-
-
#define MAX_WEIGHT 0X7FFFFFFF
-
-
-
int dijkstra(int n, int adjMatrix[][n], int startV, int endV, int prev[]);
-
-
void printShortestPath(int n, int adjMatrix[][n], int startV, int endV, const char **vertexStr);
-
-
int main()
-
{
-
//char vertex[] = {'a', '1', '2', '3', '4', '5', '6', 'b'};
-
const char *vertexStr[8] = {"a", "v1", "v2", "v3", "v4", "v5", "v6", "b"};
-
int adjMatrix[8][8] = {
-
{MAX_WEIGHT, 2, 8, 1, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
-
{2, MAX_WEIGHT, 6, MAX_WEIGHT, 1, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
-
{8, 6, MAX_WEIGHT, 7, 4, 2, 2, MAX_WEIGHT},
-
{1, 7, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, MAX_WEIGHT},
-
{MAX_WEIGHT, 1, 4, MAX_WEIGHT, MAX_WEIGHT, 3, MAX_WEIGHT, 9},
-
{MAX_WEIGHT, 2, MAX_WEIGHT, MAX_WEIGHT, 3, MAX_WEIGHT, 4, 6},
-
{MAX_WEIGHT, MAX_WEIGHT, 2, 9, MAX_WEIGHT, 4, MAX_WEIGHT, 2},
-
{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, 6, 2, MAX_WEIGHT}
-
};
-
/*
-
int adjMatrix[8][8] = {
-
//{0, 1, 2, 3, 4, 5, 6, 7}
-
{0, 2, 8, 1, 0, 0, 0, 0},
-
{2, 0, 6, 0, 1, 0, 0, 0},
-
{8, 6, 0, 7, 4, 2, 2, 0},
-
{1, 7, 0, 0, 0, 0, 9, 0},
-
{0, 1, 4, 0, 0, 3, 0, 9},
-
{0, 2, 0, 0, 3, 0, 4, 6},
-
{0, 0, 2, 9, 0, 4, 0, 2},
-
{0, 0, 0, 0, 9, 6, 2, 0}
-
};
-
*/
-
-
/*
-
int prev[8];
-
int shortestPath = dijkstra(8, adjMatrix, 0, 7, prev);
-
printf("the sum of shortest weight is %d\n", shortestPath);
-
*/
-
printShortestPath(8, adjMatrix, 0, 7, vertexStr);
-
-
return 0;
-
}
-
-
-
/******************************************************
-
*Fuction:
-
* 求图最短路径长度,并存储迹
-
* Input:
-
* n--顶点个数
-
* adjMatrix[n][n]--图的邻接矩阵
-
* startV--源点
-
* endV--结束点
-
* prev[i]记录从源到顶点的最短路径上i的前一个顶点
-
*Out:
-
* 输出最短路径长度
-
* ******************************************************/
-
-
int dijkstra(int n, int adjMatrix[][n], int startV, int endV, int prev[n])
-
{
-
int dist[n]; //dist[i]表示从源到顶点i的最短特殊路径长度
-
int mask[n]; //mask[i]标记顶点i是否加入集合 -1表示已加入集合
-
int shortestPath = 0;
-
int minWeight = MAX_WEIGHT;
-
int minID;
-
int i;
-
int j;
-
int tmp = 0;
-
-
for (i=0; i<n; i++)
-
{
-
mask[i] = 0; //初始化集合为空集,即没有元素加入
-
dist[i] = adjMatrix[startV][i]; //初始化dist[j]
-
prev[i] = -1;
-
prev[i] = (adjMatrix[startV][i] != MAX_WEIGHT) ? startV : -1;
-
}
-
-
-
//prev[0] = startV;
-
// dist[startV] = -1; //起点标记为-1 不被更新
-
mask[startV] = -1; //标记源点已加入
-
-
for (i=1; i<n; i++) //最多再加入n-1个顶点
-
{
-
minWeight = MAX_WEIGHT;
-
//寻找下一个待加入的顶点
-
for (j=0; j<n; j++)
-
{
-
if (mask[j]!=-1 && dist[j]<minWeight)
-
{
-
minWeight = dist[j];
-
minID = j;
-
}
-
}
-
-
mask[minID] = -1; //加入顶点
-
-
if (minID == endV) //最后一个节点已加入
-
{
-
return dist[endV];
-
}
-
-
//更新dist[i]
-
for (j=0; j<n; j++)
-
{
-
if (minWeight==MAX_WEIGHT || adjMatrix[minID][j]==MAX_WEIGHT)
-
continue;
-
tmp = minWeight + adjMatrix[minID][j];
-
if(j!=startV && tmp<dist[j]) //起点无须更新
-
{
-
dist[j] = tmp;
-
prev[j] = minID;
-
}
-
}
-
-
}
-
-
}
-
-
//print path
-
void printShortestPath(int n, int adjMatrix[][n], int startV, int endV, const char **vertexStr)
-
{
-
int prev[n];
-
int shortestPath = dijkstra(n, adjMatrix, startV, endV, prev);
-
printf("the shortest path is: %d= ", shortestPath);
-
int tmp = endV;
-
do
-
{
-
printf("%s <--- ", vertexStr[tmp]);
-
tmp = prev[tmp];
-
}while(tmp != startV);
-
printf("%s\n", vertexStr[startV]);
-
-
}
三、测试结果
- the shortest path is: 11= b <--- v6 <--- v2 <--- v4 <--- v1 <--- a
阅读(2372) | 评论(0) | 转发(0) |