数据结构中，最短路径一定是简单路径吗?也就是说：最短路径中能不能出现环路？ 关于数据结构中最短路径问题
\u6700\u77ed\u8def\u5f84\u4e00\u5b9a\u662f\u7b80\u5355\u8def\u5f84\u5417?\u4ec0\u4e48\u662f\u7b80\u5355\u8def\u5f84 \u662f \u7ecf\u8fc7\u70b9\u6570\u6700\u5c11\u7684\u5417
\u5982\u679c\u662f\u7684\u8bdd \u90a3\u4e48 \u65e0\u6743\u7684010101\u6700\u77ed\u8def\u5f84 \u5c31\u4e00\u5b9a \u6709\u6743\u7684\u5c31\u4e0d\u4e00\u5b9a\u4e86
\u95ee\u9898 1: \u521b\u5efa\u666f\u70b9\u56fe\u7684\u51fd\u6570initgraph()\u91cc,\u56e0\u4e3a\u90bb\u63a5\u77e9\u9635\u662f\u5bf9\u79f0\u77e9\u9635,\u6240\u4ee5\u8981\u5bf9\u79f0\u8d4b\u503c, \u5fc5\u987b\u662f\u7528\u8bed\u53e5 c->arcs[j][i].adj=c->arcs[i][j].adj; \u6ce8\u610f,\u662f[j][i]\u5728\u524d, \u800c[i][j]\u5728\u540e. \u800c\u4e0d\u662fc->arcs[i][j].adj=c->arcs[j][i].adj;//\u9519\u8bef\u95ee\u9898 2: \u51fd\u6570allpath()\u80fd\u8ba1\u7b97\u51fa\u6700\u77ed\u8def\u5f84\u7684\u603b\u7ebf\u8def\u957f\u5ea6,\u4f46\u662f,\u663e\u793a\u7684\u4e2d\u9014\u7ecf\u8fc7\u7684\u9876\u70b9\u4e0d\u5bf9.\u4ee3\u7801\u7684\u4fee\u6539\u65b9\u6848:\u5bf9\u4e8e"\u4efb\u610f\u4e00\u70b9\u4e0e\u5176\u5b83\u5404\u70b9\u7684\u6700\u77ed\u8def\u5f84"\u7684\u95ee\u9898,\u53ef\u4ee5\u7528\u8fea\u6770\u65af\u7279\u62c9(Dijkstra)\u7b97\u6cd5,\u4e5f\u53ef\u4ee5\u7528\u5f17\u6d1b\u4f0a\u5fb7(Floyd)\u7b97\u6cd5,\u4ee5\u4e0b\u662f\u4fee\u6539\u540e\u7684\u4ee3\u7801,\u63d0\u4f9b\u4e24\u4e2a\u65b9\u6848:void allpath_Floyd(mgraph c) //\u65b9\u68481:Floyd\u7b97\u6cd5void allpath_Dijkstra(mgraph c) //\u65b9\u68482:Dijkstra\u7b97\u6cd5\u5982\u679c\u6709\u4efb\u4f55\u95ee\u9898,\u53ef\u4ee5\u767e\u5ea6\u79c1\u4fe1\u7ed9\u6211.#include "stdio.h"#include "string.h"#define Infinity 9999#define MaxVertexNum 20typedef struct arcell //\u8fb9\u7684\u4fe1\u606f{ int adj; //\u6743\u503c}arcell,adjmatrix[MaxVertexNum][MaxVertexNum];typedef struct vexsinfo //\u9876\u70b9\u4fe1\u606f{ int position; //\u666f\u70b9\u7684\u7f16\u53f7 char name[32]; //\u666f\u70b9\u540d char introduction[56]; //\u666f\u70b9\u7684\u4ecb\u7ecd}vexsinfo;typedef struct mgraph//\u4f7f\u7528\u90bb\u63a5\u77e9\u9635\u5b9e\u73b0\u56fe\u7684\u5b58\u50a8{ vexsinfo vexs[MaxVertexNum];//\u6570\u7ec4\u9876\u70b9\u5411\u91cf,\u5b58\u9876\u70b9\u4fe1\u606f adjmatrix arcs; //\u90bb\u63a5\u77e9\u9635 int vexnum,arcnum; //\u9876\u70b9\u6570\u548c\u8fb9\u6570}mgraph;mgraph c; //\u5168\u5c40\u53d8\u91cf//\u521b\u5efa\u666f\u70b9\u56fe (\u8f93\u5165\u53c2\u6570\u662f\u6307\u9488)void initgraph(mgraph *c){ int i,j; c->vexnum=6; //\u9876\u70b9\u7684\u603b\u6570\u91cf c->arcnum=8; //\u8fb9\u7684\u603b\u6570\u91cf for(i=0;ivexnum;i++)//\u8bbe\u7f6e\u9876\u70b9\u7f16\u53f7 { c->vexs[i].position=i; } strcpy(c->vexs[0].name,"v1"); strcpy(c->vexs[1].name,"v2"); strcpy(c->vexs[2].name,"v3"); strcpy(c->vexs[3].name,"v4"); strcpy(c->vexs[4].name,"v5"); strcpy(c->vexs[5].name,"v6"); //\u5148\u521d\u59cb\u5316\u56fe\u7684\u90bb\u63a5\u77e9\u9635 for(i=0;ivexnum;i++) { for(j=0;jvexnum;j++) { c->arcs[i][j].adj=Infinity; } }c->arcs[0][1].adj=7;c->arcs[0][2].adj=11;c->arcs[1][2].adj=10;c->arcs[1][3].adj=9;c->arcs[2][3].adj=5;c->arcs[2][4].adj=7;c->arcs[2][5].adj=8;c->arcs[4][5].adj=6;//\u90bb\u63a5\u77e9\u9635\u662f\u5bf9\u79f0\u77e9\u9635,\u5bf9\u79f0\u8d4b\u503c for(i=0;ivexnum;i++) { for(j=0;jvexnum;j++) { //\u6ce8\u610f,\u662f[j][i]\u5728\u524d, \u800c[i][j]\u5728\u540e. c->arcs[j][i].adj=c->arcs[i][j].adj; } }}//\u67e5\u770b\u666f\u70b9\u95f4\u7684\u8def\u7ebf [\u9700\u8981\u6539\u5584]void allpath(mgraph c){ //\u6c42\u4ece\u9876\u70b9v0\u5230\u5176\u4f59\u9876\u70b9\u7684\u6700\u77ed\u8def\u5f84p[]\u53ca\u5e26\u6743\u957f\u5ea6d[v]\uff08\u6700\u77ed\u8def\u5f84\u7684\u8ddd\u79bb\uff09 //p[][]\u6570\u7ec4\u7528\u4e8e\u5b58\u653e\u4e24\u9876\u70b9\u95f4\u662f\u5426\u6709\u901a\u8def\u6807\u8bc6\uff0c\u5982\u679cp[v][w]=1\uff0c\u5219w\u662f\u4ecev0\u5230v\u7684\u6700\u77ed\u8def\u5f84\u4e0a\u7684\u9876\u70b9 //visited[\u6570\u7ec4\u7528\u4e8e\u8bbe\u7f6e\u8bbf\u95ee\u6807\u5fd7 int v,w,i,min,t=0,x; //\u53d8\u91cft\u6ca1\u6709\u4f7f\u7528 int v0;//v0\u4e3a\u8d77\u59cb\u666f\u70b9\u7684\u7f16\u53f7 int visited[20],d[20],p[20][20]; printf("\n\u8bf7\u8f93\u5165\u4e00\u4e2a\u8d77\u59cb\u666f\u70b9\u7684\u7f16\u53f7:"); scanf("%d",&v0); printf("\n\n"); while(v0c.vexnum) { printf("\n\u60a8\u8f93\u5165\u7684\u666f\u70b9\u4e0d\u5b58\u5728\n"); printf("\u8bf7\u91cd\u65b0\u8f93\u5165\uff1a"); scanf("%d",&v0); } for(v=0;v%s",c.vexs[v].name); } printf("---->%s",c.vexs[v].name); printf("\n\u603b\u8def\u7ebf\u957f\u4e3a%d\u7c73:\n\n",d[v]); }}//\u8f93\u51fa\u4efb\u610f\u4e00\u70b9\u4e0e\u5176\u5b83\u5404\u70b9\u7684\u6700\u77ed\u8def\u5f84//\u7b97\u6cd5: \u5f17\u6d1b\u4f0a\u5fb7(Floyd)void allpath_Floyd(mgraph c){ int v,w,k; int v0; //\u8f93\u5165\u7684\u8d77\u59cb\u9876\u70b9\u7f16\u53f7 int P[MaxVertexNum][MaxVertexNum]; //\u4e8c\u7ef4\u6570\u7ec4P\u7528\u4e8e\u8bb0\u5f55\u4e24\u70b9\u4e4b\u95f4\u7684\u8def\u5f84\u4e0b\u6807 int D[MaxVertexNum][MaxVertexNum]; //\u4e8c\u7ef4\u6570\u7ec4D\u7528\u4e8e\u8bb0\u5f55\u6bcf\u6761\u8fb9\u7684\u6743\u503c(\u4e5f\u5c31\u662f\u8ddd\u79bb) while(1) { printf("\u8bf7\u8f93\u5165\u4e00\u4e2a\u8d77\u59cb\u666f\u70b9\u7684\u7f16\u53f7(%d\u5230%d): ",0,c.vexnum-1); scanf("%d",&v0); //\u666f\u70b9\u56fe\u6709c.vexnum\u4e2a\u9876\u70b9,\u7f16\u53f7\u4ece0\u5230(c.vexnum-1) if(v0= c.vexnum) { printf("\u666f\u70b9\u7684\u7f16\u53f7\u4e0d\u5b58\u5728!\u8bf7\u91cd\u65b0\u8f93\u5165\u7f16\u53f7\n"); continue; //\u76f4\u63a5\u8df3\u5230while()\u8bed\u53e5,\u7ee7\u7eed\u5faa\u73af } else { break; } } //\u5bf9\u6570\u7ec4D\u548c\u6570\u7ec4P\u8fdb\u884c\u521d\u59cb\u5316 for(v=0; v (D[v][k]+D[k][w]) ) { //\u5982\u679c\u7ecf\u8fc7\u4e0b\u6807\u4e3ak\u9876\u70b9\u8def\u5f84\u6bd4\u539f\u4e24\u70b9\u95f4\u8def\u5f84\u66f4\u77ed, //\u90a3\u4e48,\u5c31\u5c06\u5f53\u524d\u4e24\u70b9\u95f4\u6743\u503c\u8bbe\u4e3a\u66f4\u5c0f\u7684\u4e00\u4e2a\u8def\u5f84\u8bbe\u7f6e\u4e3a\u7ecf\u8fc7\u4e0b\u6807\u4e3ak\u7684\u9876\u70b9 D[v][w]=D[v][k]+D[k][w]; P[v][w]=P[v][k]; } } } } v=v0; //v0\u662f\u8d77\u59cb\u9876\u70b9\u7f16\u53f7 for(w=0; w%s",c.vexs[k].name); //\u6253\u5370\u8def\u5f84"\u7ecf\u8fc7\u7684\u9876\u70b9"\u7684\u540d\u79f0 k=P[k][w]; //\u83b7\u5f97"\u4e0b\u4e00\u4e2a"\u8def\u5f84\u9876\u70b9\u4e0b\u6807 } printf("-->%s",c.vexs[w].name); //\u6253\u5370"\u7ec8\u70b9"\u7684\u540d\u79f0 printf(" \u603b\u8def\u7ebf\u957f%dm",D[v][w]); printf("\n\n"); }}//\u8f93\u51fa\u4efb\u610f\u4e00\u70b9\u4e0e\u5176\u5b83\u5404\u70b9\u7684\u6700\u77ed\u8def\u5f84//\u7b97\u6cd5: \u8fea\u6770\u65af\u7279\u62c9(Dijkstra)void allpath_Dijkstra(mgraph c){ int v0; //\u8f93\u5165\u7684\u8d77\u59cb\u9876\u70b9\u7f16\u53f7 int w0; int v,w,k,min; int qty; int finalData[MaxVertexNum]; //finalData[w]=1\u8868\u793a\u5df2\u7ecf\u6c42\u5f97\u8d77\u59cb\u9876\u70b9v0\u5230vw(w\u662f\u4e0b\u6807)\u7684\u6700\u77ed\u8def\u5f84 int P[MaxVertexNum]; //\u6570\u7ec4P\u7528\u4e8e\u8bb0\u5f55\u4e24\u70b9\u4e4b\u95f4\u7684\u8def\u5f84\u4e0b\u6807 int D[MaxVertexNum]; //\u6570\u7ec4D\u7528\u4e8e\u5b58\u50a8\u5230\u5404\u70b9\u6700\u77ed\u8def\u5f84\u7684\u6743\u503c\u548c int PathBuf[MaxVertexNum]; //\u5b58\u5165\u6309\u987a\u5e8f\u7684\u8def\u5f84\u4e0b\u6807(\u7528\u4e8e\u5c4f\u5e55\u663e\u793a) while(1) { printf("\u8bf7\u8f93\u5165\u4e00\u4e2a\u8d77\u59cb\u666f\u70b9\u7684\u7f16\u53f7(%d\u5230%d): ",0,c.vexnum-1); scanf("%d",&v0); //\u666f\u70b9\u56fe\u6709c.vexnum\u4e2a\u9876\u70b9,\u7f16\u53f7\u4ece0\u5230(c.vexnum-1) if(v0= c.vexnum) { printf("\u666f\u70b9\u7684\u7f16\u53f7\u4e0d\u5b58\u5728!\u8bf7\u91cd\u65b0\u8f93\u5165\u7f16\u53f7\n"); continue; //\u76f4\u63a5\u8df3\u5230while()\u8bed\u53e5,\u7ee7\u7eed\u5faa\u73af } else { break; } } for(v=0; v =1 ; k--) { printf("%s-->",c.vexs[PathBuf[k]].name); } printf("%s",c.vexs[PathBuf[k]].name); printf(" \u603b\u8def\u7ebf\u957f%dm",D[w0]); printf("\n\n"); }}int main(void){ //\u521b\u5efa\u666f\u70b9\u56fe initgraph(&c); //\u8f93\u5165\u53c2\u6570\u662f\u6307\u9488 //\u67e5\u770b\u666f\u70b9\u95f4\u7684\u8def\u7ebf allpath_Floyd(c); //\u65b9\u68481: Floyd\u7b97\u6cd5 //allpath_Dijkstra(c); //\u65b9\u68482: Dijkstra\u7b97\u6cd5 //allpath(c); //\u539f\u4ee3\u7801[\u9700\u8981\u6539\u5584]return 0;}
最短路径中不会出现环路。可以在有环图里求最短路径，但最短路径里肯定没环啊。
最短路径肯定是简单路径啊，这很好想吧。。
考虑单源最短路径问题，假设一个3个节点带负权的环路，
1→2权为1，2→3权为-4，3→1权为2，一般情况下，如果不允许负权边，那么1节点到自身的最短路径就是0，但在有负环的情况下，1节点到自身的最短路径为：1→2→3=-1，形成环路。
数据结构王道考研书 244页 第10题 第五行 写明了 最短路径是允许有环的
有环路就不叫最短路径了
绛旓細鏈鐭矾寰涓笉浼氬嚭鐜扮幆璺
绛旓細鍥炵瓟锛氭湁鐜矾灏变笉鍙鏈鐭矾寰浜
绛旓細婧愮偣锛圫ource锛 璺緞鐨勫紑濮嬮《鐐 缁堢偣锛圖estination锛 璺緞鐨勬渶鍚庝竴涓《鐐 鍗曟簮鏈鐭矾寰勯棶棰锛圫ingle Source Shortest Paths Problem锛 缁欏畾涓涓甫鏉冨浘G=(V E)鍜屽浘涓殑涓涓簮鐐箆 鍒嗗埆姹傚嚭浠巚鍒板浘G涓叾浠栨瘡涓《鐐圭殑鏈鐭矾寰勯暱搴 鍗宠矾寰勪笂鏉冨肩殑鎬诲拰 鍗曠洰鏍囨渶鐭矾寰勯棶棰橈紙Single Destination Shortest P...
绛旓細浠庢簮鐐瑰埌缁堢偣鎵鍚竟鐨勬暟鐩渶灏戠殑璺緞绉颁负鏈鐭矾寰銆
绛旓細Dijkstra)绠楁硶姝ラ锛氾紙姹傚浘涓璿0鍒皏8鐨鏈鐭矾寰锛夊苟闈炰竴涓嬪瓙姹傚嚭v0鍒皏8鐨勬渶鐭矾寰勶紝鑰屾槸 涓姝ヤ竴姝ユ眰鍑哄畠浠箣闂撮《鐐圭殑鏈鐭矾寰 锛岃繃杩囩▼涓兘鏄 鍩轰簬宸茬粡姹傚嚭鐨勬渶鐭矾寰勭殑鍩虹涓婏紝姹傚緱鏇磋繙椤剁偣鐨勬渶鐭矾寰勶紝鏈缁堝緱鍑烘簮鐐逛笌缁堢偣鐨勬渶鐭矾寰 銆傚紬娲涗紛寰(Floyd)绠楁硶鏄竴涓粡鍏哥殑 鍔ㄦ佽鍒掔畻娉 銆
绛旓細int distance[N]; // 鐢ㄤ簬瀛樻斁璧峰鐐瑰埌鍏朵綑鍚勭偣鐨勬渶鐭窛绂 int path[N]; // 鐢ㄤ簬瀛樻斁璧峰鐐瑰埌鍏朵綑鍚勭偣鏈鐭矾寰鐨勫墠涓涓《鐐 int used[N] = { 0 }; // 鐢ㄤ簬鏍囪璇ラ《鐐规槸鍚﹀凡缁忔壘鍒版渶鐭矾寰 int i, j, min_node, min_dis, pass_flag = 0;for(i = 0; i < N; i++){ distance...
绛旓細鏈鐭矾寰鏍戞槸涓绉嶅湪鍥惧舰鐞嗚涓父鐢ㄧ殑鏁版嵁缁撴瀯锛屼富瑕佺敤浜庤В鍐冲湪涓涓繛閫氬浘涓鎵句袱涓妭鐐逛箣闂寸殑鏈鐭矾寰勯棶棰樸傚湪璁＄畻鏈虹瀛︺佺綉缁溿佷氦閫氱瓑棰嗗煙涓紝鏈鐭矾寰勬爲鐨勫簲鐢ㄩ潪甯稿箍娉涖傝缁嗚В閲婂涓嬶細1. 鍩烘湰姒傚康锛氭渶鐭矾寰勬爲鏄竴绉嶇敓鎴愭爲绠楁硶锛屽畠鑳藉鏍规嵁鍥剧殑杈规潈閲嶆瀯寤轰竴妫靛寘鍚浘涓墍鏈夎妭鐐圭殑鏍戯紝骞朵笖杩欐５鏍戜笂...
绛旓細浠ユ暟鎹粨鏋勪负渚嬶紝鏈灏忕敓鎴愭爲鍜鏈鐭矾寰鐨勫尯鍒槸鏈灏忕敓鎴愭爲鑳藉淇濊瘉鏁翠釜鎷撴墤鍥剧殑鎵鏈夎矾寰勪箣鍜屾渶灏忥紝浣嗕笉鑳戒繚璇佷换鎰忎袱鐐逛箣闂存槸鏈鐭矾寰勩傛渶鐭矾寰勬槸浠庝竴鐐瑰嚭鍙戯紝鍒拌揪鐩殑鍦扮殑璺緞鏈灏忋傛暟鎹粨鏋勶紙datastructure锛夋槸璁＄畻鏈哄瓨鍌ㄣ佺粍缁囨暟鎹殑鏂瑰紡锛屾寚鐩镐簰涔嬮棿瀛樺湪涓绉嶆垨澶氱鐗瑰畾鍏崇郴鐨勬暟鎹厓绱犵殑闆嗗悎锛屽線寰鍚...
绛旓細鍦ㄨ绠楁満绉戝涓紝瑙ｅ喅鏈鐭矾寰闂鐨勭畻娉曡骞挎硾绉颁负"鏈鐭矾寰勭畻娉"锛屾湁鏃剁畝绉颁负"璺緞绠楁硶"锛屽叾涓寘鎷绉嶅父鐢ㄦ柟娉曪細Dijkstra绠楁硶銆丄*绠楁硶銆丼PFA绠楁硶銆丅ellman-Ford绠楁硶銆丗loyd-Warshall绠楁硶鍜孞ohnson绠楁硶銆傝繖浜涚畻娉曚富瑕佸簲鐢ㄤ簬鎵惧嚭鍥綠=(V,E)涓紝浠庣壒瀹氭簮鑺傜偣S鍒版墍鏈夊叾浠栬妭鐐圭殑鏈鐭矾寰勩傚叾涓紝Dijkstra绠楁硶...
绛旓細鏈灏忕敓鎴愭爲鏄鎵惧埌鏈灏忕殑杈瑰彲浠ユ妸鎵鏈夌殑鑺傜偣閮借繛鎺ヨ捣鏉,鑰屾渶鐭矾寰勬槸 瑕佹眰鏌愪釜鑺傜偣鍒板叾浣欒妭鐐圭殑鏈鐭殑璺緞銆 鏈灏忕敓鍜告爲: 鍦ㄤ竴缁欏畾鐨勬棤鍚戝浘G=(V,E)涓,(u,v)浠ｈ〃杩炴帴椤剁偣u涓庨《鐐箆鐨勮竟(鍗),鑰寃(u,v)浠ｈ〃姝よ竟鐨勬潈閲,鑻ュ瓨鍦═涓篍鐨勫瓙闆(鍗)涓斾负鏃犲惊鐜浘,浣垮緱w(T)鏈灏,鍒欐T涓篏鐨勬渶灏忕敓鎴愭爲銆
