迪杰斯特拉算法求得最短路径唯一么
当然唯一，特定算法只能产生特定结果，除非你更改了算法中的一些细节，比如节点的访问顺序之类的。
不过最短路径不唯一，而且Dijkstra算法不可能精确到所有的算法细节，所以你这个问题我没看出来有什么意义。
怎样实现迪杰斯特拉算法求最短路径功能的
鉴于最小生成树和最短路径的dijkstra是相似的，我把它们合到一块了，另外下面附了一个用堆优化的dijkstra（优先队列）的代码，看看吧。
最小生成树的普利姆算法和求最短路径的dijkstra算法算法思想：1.、先将出发点（对最小生成树来说可以是任意一点）放入集合s中（s为元素为图的顶点的集合，记录已经解决的顶点）。
2、找到s外的所有点到s的距离（即到s中所有点的距离的最小值）最小的点，把这一点加入s集合。
3、由于新加入的一个点会使某些点到s的距离更短，更新s外的其他点到集合s的距离（如果可以更短，则更新之）。
4、返回执行第2步，直到所有的点都加入s中。
注：第二步找到的最短距离会逐步增加，所以此算法也可以解决例如第K远的城市这种问题算法代码：int const MAXN = 100;int i,j;int n; \\\/\\\/记录图的顶点个数int edge[MAXN][MAXN]; \\\/\\\/记录各边权值, 默认无向并且已知，两点之间无边则记为无穷大int dist[MAXN]; \\\/\\\/记录当前各个点到集合s的最小距离，在运行过程中不断更新 int s[MAXN] = {0}; \\\/\\\/记录已经解决的点的下标,标志着该顶点是否加入最小生成树\\\/\\\/初始化，假设各边权值已知，出发点为0for(i = 0; i < n; i++){ dist[i] = edge[0][i];}\\\/*执行第一步*\\\/s[0] = 1;for(i = 0; i < n - 1; i++)\\\/\\\/循环n-1次将剩余的n-1个点加入生成树{ \\\/*执行第二步*\\\/ int min = inf; \\\/\\\/ inf 为可能的最大值 int u = 0; \\\/\\\/ 记录距离s最短的顶点的下标 for(j = 0; j < n; j++) { if(!s[j] && dist[j] < min) { min = dist[j]; u = j; } } s[u] = 1; \\\/*执行第三步*\\\/ \\\/*************最小生成树的普利姆*********************\\\/ for(j = 0; j < n; j++) { if(!s[j] && edge[u][j] < dist[j]) dist[j] = edge[u][j]; } \\\/****************************************************\\\/ \\\/************最短路径的dijstra算法********************\\\/ for(j = 0; j < n; j++) { if( !s[j] && dist[u] + edge[u][j] < dist[j]) dist[j] = dist[u] + edge[u][j]; } \\\/***************************************************\\\/}附：\\\/*dijkstra priority_queue 邻接链表实现*\\\/#include #include using namespace std;const int MAXN = 110;int head[MAXN],size;int dist[MAXN];int n; struct enode{ int v,cost,next; enode(){} enode(int _v,int _cost):v(_v),cost(_cost){} enode(int _v, int _cost, int _next):v(_v), cost(_cost), next(_next){} bool operator < (const enode &t) const{ return cost > t.cost; }};enode edges[MAXN*MAXN];void add_edge(int u,int v,int cost){ edges[size] = enode(v,cost,head[u]); head[u] = size++;}int init(){ int m,u,v,c; memset(head,-1,sizeof(head)); size = 0; scanf(%d%d,&n,&m); \\\/\\\/输入顶点数和边数 if(m == 0 && n == 0)return 0; for(int i = 0; i < m; i++){ scanf(%d%d%d,&u,&v,&c); \\\/\\\/输入边的两个顶点和边的权值 add_edge(u-1,v-1,c); add_edge(v-1,u-1,c); } return 1;}void Dijkstra(int st){ memset(dist,0x3f,sizeof(dist)); dist[st] = 0; priority_queue < enode > q; q.push( enode(st,0) ); while ( !q.empty() ){ enode top = q.top(); q.pop(); if(top.cost != dist[top.v]) continue; int u,v; u = top.v; for(int i = head[u] ;i != -1; i = edges[i].next){ v = edges[i].v; if ( dist[v] > dist[u] + edges[i].cost ){ dist[v] = dist[u] + edges[i].cost; q.push( enode(v,dist[v]) ); } } }}int main(){ while( init() ){ Dijkstra(0); printf(%d\\\ ,dist[n-1]); } return 0;}
求顶点之间的最短路径，要求实现迪杰斯特拉算法和弗洛伊德算法
你可以看一下这个链接，对你会助：（Dijkstra算法（Floyd算法）你是大学的学生吧，别人的东西都是别人的，你来学习的时候是自己一下，加深理解，这个很重要，我就不给你实现了，于你没什么好处，而且也没必要，呵呵，加油。
求迪杰斯特拉算法最短路径的算法，有输入与输出算法的C语言编程，谢谢
输入和输出是用邻接矩阵描述的图么，如果是的话我把我的代码COPY给你：#include #include #define INFINITY 9999#define MAX_VERTEX_NUM 20typedef struct{ int vexs[MAX_VERTEX_NUM]; int arcs[20][20]; int vexnum,arcnum;}MGraph;void ShortestPath_DIJ(MGraph G,int v0,int D[]){ int *final,min,i,v,w,vex,path[20],j,path2[20]; printf(输入要到达的顶点：); scanf(%d,&vex); final=(int *)malloc(sizeof(int)*G.vexnum); for(v=0;v=0;w--){ if(path[vex]==-1){ printf(%d到%d间不存在可行路径,v0,vex); break; } if(path2[w]!=-1) printf(%d ,path2[w]); } printf(\\\ ); printf(\\\ );}int main(){ int D[20],i,j,v0; MGraph G; for(i=0;i<20;i++) G.vexs[i]=i; for(i=0;i<20;i++) for(j=0;j<20;j++) G.arcs[i][j]=INFINITY; G.vexnum=6;G.arcnum=8; G.arcs[0][2]=10;G.arcs[0][4]=30; G.arcs[0][5]=100;G.arcs[1][2]=5; G.arcs[2][3]=50;G.arcs[3][5]=10; G.arcs[4][3]=20;G.arcs[4][5]=60; for(i=0;i数据结构 C++ 迪杰斯特拉算法最短路径求补充完整。
分还可以再加
#include int line;\\\/\\\/结点之间的路径数int n ; \\\/\\\/实际结点数，我们通过键盘输入const int maxnum = 15; \\\/\\\/支持的最大节点数int cost[maxnum][maxnum] = {0}; \\\/\\\/两点之间的直线距离,最好初始化为无穷大int s[maxnum] = {0}; \\\/\\\/s 判断结点是否在s集合里int dist[maxnum]; \\\/\\\/ 表示当前点到源点的长度int path[maxnum][maxnum];int MINDIST(int s[],int dist[]){ int temp=100000 , i, w = 2; for(i = 2;i <= n; i++) { if(s[i] == 0 && dist[i] < temp) { temp = dist[i]; w = i; } } return w;}int SEARCH_VER(int s[],int dist[],int u){static int j = 0;for(; j<=n; )if(s[j] == 0 && cost[u][j]<100000) {j++;return j-1;}else{j++;}return -1;}void SHORTEST_PATH(int cost[][maxnum],int v,int last,int dist[],int path[][maxnum]){int i,w,u,count,pos[maxnum];for(i=0;i我研究了一下午，只研究了这么多，但是path是做什么用的，我真的不知道，我可以改成其他的实现方法吗
