资源简介
目前网络上电子地图的使用很普遍。利用电子地图可以很方便地确定从一个地点到另一个地点的路径。特别地,可确定在城市中的公交换乘路线。
电子地图可以看成是一个图,而公交线路图可看成是带权有向图G =(V,E),其中每条边的权是非负实数。
最短路径问题:计算从给定的起点s到另一个顶点t的最短路径的长度。
你的任务:对给定的一个(无向)图G,及G中的两点s、t,计算从起点s到顶点t的最短距离。
代码片段和文件信息
/*#include
#include
using namespace std;
void Dijkstra(int nint vint dist[]int prev[]int **c)
{
int maxint = 65535;
//int maxint = -1;
bool *s = new bool[n];
for (int i = 1; i <= n; i++)
{
dist[i] = c[v][i];
s[i] = false;
if (dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
}
dist[v] = 0;
s[v] = true;
for (int i = 1; i < n; i++)
{
int temp = maxint;
int u = v;
for (int j = 1; j <= n; j++)
{
if ((!s[j]) && (dist[j] < temp))
//if ((!s[j]) && (dist[j] >= temp))
{
u = j;
temp = dist[j];
}
}
s[u] = true;
for (int j = 1; j <= n; j++)
{
if ((!s[j]) && (c[u][j] < maxint))
//if ((!s[j]) && (c[u][j] >= maxint))
{
属性 大小 日期 时间 名称
----------- --------- ---------- ----- ----
文件 3654 2015-07-03 18:09 4-c\4-c.cpp
文件 1433 2015-07-03 18:09 4-c\4-c.msp
目录 0 2015-07-04 14:11 4-c\Debug\
文件 547378 2015-07-03 18:09 4-c\Debug\4-c.exe
文件 126698 2015-07-03 18:09 4-c\Debug\4-c.o
目录 0 2015-07-04 14:11 4-c\
- 上一篇:数据库及ADO.NET(ppt)
- 下一篇:dmieditwin32
评论
共有 条评论