![\"\"](\"https:\/\/cn.hostease.com\/xueyuan\/wp-content\/uploads\/2017\/04\/Dijkstra.png\")
<\/a><\/figure>\n\n\n\n<\/p>\n\n\n\n
\u9996\u5148\u6211\u4eec\u5206\u6790\u4e0bDijkstra\u7b97\u6cd5\u7684\u6b65\u9aa4\uff1a<\/p>\n\n\n\n
\u6709\u96c6\u5408M={V0,V1,V2,V3,V4}\u8fd9\u68375\u4e2a\u5143\u7d20\uff0c\u6211\u4eec\u7528<\/p>\n\n\n\n
TempVertex\u8868\u793a\u8be5\u9876\u70b9\u662f\u5426\u4f7f\u7528\u3002<\/p>\n\n\n\n
Weight\u8868\u793a\u8be5Path\u7684\u6743\u91cd(\u9ed8\u8ba4\u90fd\u4e3aMaxValue)\u3002<\/p>\n\n\n\n
Path\u8868\u793a\u8be5\u9876\u70b9\u7684\u603b\u6743\u91cd\u3002<\/p>\n\n\n\n
\u2460. \u4ece\u96c6\u5408M\u4e2d\u6311\u9009\u9876\u70b9V0\u4e3a\u8d77\u59cb\u70b9\u3002\u7ed9V0\u7684\u6240\u6709\u90bb\u63a5\u70b9\u8d4b\u503c\uff0c\u8981\u8d4b\u503c\u7684\u524d\u63d0\u662f\u8981\u8d4b\u503c\u7684weight\u8981\u5c0f\u4e8e\u539f\u59cb\u7684weight\uff0c\u5e76\u4e14\u6392\u9664\u5df2\u7ecf\u8bbf\u95ee\u8fc7<\/p>\n\n\n\n
\u7684\u9876\u70b9\uff0c\u7136\u540e\u6311\u9009\u5f53\u524d\u6700\u5c0f\u7684weight\u4f5c\u4e3a\u4e0b\u4e00\u6b21\u8d2a\u5fc3\u641c\u7d22\u7684\u8d77\u70b9\uff0c\u5c31\u8fd9\u6837V0V1\u4e3a\u6311\u9009\u4e3a\u6700\u77ed\u8def\u5f84\uff0c\u5982\u56fe2\u3002<\/p>\n\n\n\n
\u2461. \u6211\u4eec\u7ee7\u7eed\u4eceV1\u8fd9\u4e2a\u9876\u70b9\u5f00\u59cb\u7ed9\u90bb\u63a5\u70b9\u4ee5\u540c\u6837\u7684\u65b9\u5f0f\u8d4b\u503c\uff0c\u6700\u540e\u6211\u4eec\u53d1\u73b0V0V4\u4e3a\u6700\u77ed\u8def\u5f84\u3002\u4e5f\u5c31\u662f\u56fe3\u3002<\/p>\n\n\n\n
\u3002\u3002\u3002<\/p>\n\n\n\n
\u2462. \u6700\u540e\u6240\u6709\u9876\u70b9\u7684\u6700\u77ed\u8def\u5f84\u5c31\u8fd9\u6837\u6c42\u51fa\u6765\u4e86 \u3002<\/p>\n\n\n\n
\n
1 #region Dijkstra\u7b97\u6cd5\n 2 \/\/\/ <summary>\n 3 \/\/\/ Dijkstra\u7b97\u6cd5\n 4 \/\/\/ <\/summary>\n 5 public Dictionary<int, Edge> Dijkstra()\n 6 {\n 7 \/\/\u6536\u96c6\u9876\u70b9\u7684\u76f8\u90bb\u8fb9\n 8 Dictionary<int, Edge> dic_edges = new Dictionary<int, Edge>();\n 9 \n10 \/\/weight=MaxValue:\u6807\u8bc6\u6ca1\u6709\u8fb9\n11 for (int i = 0; i < graph.vertexsNum; i++)\n12 {\n13 \/\/\u8d77\u59cb\u8fb9\n14 var startEdge = i;\n15 \n16 dic_edges.Add(startEdge, new Edge() { weight = int.MaxValue });\n17 }\n18 \n19 \/\/\u53d6\u7b2c\u4e00\u4e2a\u9876\u70b9\n20 var start = 0;\n21 \n22 for (int i = 0; i < graph.vertexsNum; i++)\n23 {\n24 \/\/\u6807\u8bb0\u8be5\u9876\u70b9\u5df2\u7ecf\u4f7f\u7528\u8fc7\n25 dic_edges[start].isUse = true;\n26 \n27 for (int j = 1; j < graph.vertexsNum; j++)\n28 {\n29 var end = j;\n30 \n31 \/\/\u53d6\u5230\u76f8\u90bb\u8fb9\u7684\u6743\u91cd\n32 var weight = graph.edges[start, end];\n33 \n34 \/\/\u8d4b\u8f83\u5c0f\u7684\u6743\u91cd\n35 if (weight < dic_edges[end].weight)\n36 {\n37 \/\/\u4e0e\u4e0a\u4e00\u4e2a\u9876\u70b9\u7684\u6743\u503c\u7d2f\u52a0\n38 var totalweight = dic_edges[start].weight == int.MaxValue ? weight : dic_edges[start].weight + weight;\n39 \n40 if (totalweight < dic_edges[end].weight)\n41 {\n42 \/\/\u5c06\u8be5\u9876\u70b9\u7684\u76f8\u90bb\u8fb9\u52a0\u5165\u5230\u96c6\u5408\u4e2d\n43 dic_edges[end] = new Edge()\n44 {\n45 startEdge = start,\n46 endEdge = end,\n47 weight = totalweight\n48 };\n49 \n50 \/\/\u5c06\u4e0a\u4e00\u4e2a\u8fb9\u7684\u8282\u70b9\u7684vertex\u7d2f\u52a0\n51 dic_edges[end].vertexs = new HashSet<int>(dic_edges[start].vertexs);\n52 \n53 dic_edges[end].vertexs.Add(start);\n54 dic_edges[end].vertexs.Add(end);\n55 }\n56 }\n57 }\n58 \n59 var min = int.MaxValue;\n60 \n61 \/\/\u4e0b\u4e00\u4e2a\u8fdb\u884c\u6bd4\u8f83\u7684\u9876\u70b9\n62 int minkey = 0;\n63 \n64 \/\/\u53d6start\u90bb\u63a5\u8fb9\u4e2d\u7684\u6700\u5c0f\u503c\n65 foreach (var key in dic_edges.Keys)\n66 {\n67 \/\/\u53d6\u5f53\u524d \u6700\u5c0f\u7684 key(\u4f7f\u7528\u8fc7\u7684\u9664\u5916)\n68 if (min > dic_edges[key].weight && !dic_edges[key].isUse)\n69 {\n70 min = dic_edges[key].weight;\n71 minkey = key;\n72 }\n73 }\n74 \n75 \/\/\u4ece\u90bb\u63a5\u8fb9\u7684\u9876\u70b9\u518d\u5f00\u59cb\u627e\n76 start = minkey;\n77 }\n78 \n79 return dic_edges;\n80 }\n81 #endregion<\/pre>\n<\/div>\n\n\n\n\u603b\u7684\u4ee3\u7801\uff1a\u590d\u6742\u5ea6\u5f88\u70c2O(N2<\/sup>)\u3002\u3002\u3002<\/p>\n\n\n\n\n
\n
\n
\n\n\n\n1<\/div>\n 2<\/div>\n 3<\/div>\n 4<\/div>\n 5<\/div>\n 6<\/div>\n 7<\/div>\n 8<\/div>\n 9<\/div>\n 10<\/div>\n 11<\/div>\n 12<\/div>\n 13<\/div>\n 14<\/div>\n 15<\/div>\n 16<\/div>\n 17<\/div>\n 18<\/div>\n 19<\/div>\n 20<\/div>\n 21<\/div>\n 22<\/div>\n 23<\/div>\n 24<\/div>\n 25<\/div>\n 26<\/div>\n 27<\/div>\n 28<\/div>\n 29<\/div>\n 30<\/div>\n 31<\/div>\n 32<\/div>\n 33<\/div>\n 34<\/div>\n 35<\/div>\n 36<\/div>\n 37<\/div>\n 38<\/div>\n 39<\/div>\n 40<\/div>\n 41<\/div>\n 42<\/div>\n 43<\/div>\n 44<\/div>\n 45<\/div>\n 46<\/div>\n 47<\/div>\n 48<\/div>\n 49<\/div>\n 50<\/div>\n 51<\/div>\n 52<\/div>\n 53<\/div>\n 54<\/div>\n 55<\/div>\n 56<\/div>\n 57<\/div>\n 58<\/div>\n 59<\/div>\n 60<\/div>\n 61<\/div>\n 62<\/div>\n 63<\/div>\n 64<\/div>\n 65<\/div>\n 66<\/div>\n 67<\/div>\n 68<\/div>\n 69<\/div>\n 70<\/div>\n 71<\/div>\n 72<\/div>\n 73<\/div>\n 74<\/div>\n 75<\/div>\n 76<\/div>\n 77<\/div>\n 78<\/div>\n 79<\/div>\n 80<\/div>\n 81<\/div>\n 82<\/div>\n 83<\/div>\n 84<\/div>\n 85<\/div>\n 86<\/div>\n 87<\/div>\n 88<\/div>\n 89<\/div>\n 90<\/div>\n 91<\/div>\n 92<\/div>\n 93<\/div>\n 94<\/div>\n 95<\/div>\n 96<\/div>\n 97<\/div>\n 98<\/div>\n 99<\/div>\n 100<\/div>\n 101<\/div>\n 102<\/div>\n 103<\/div>\n 104<\/div>\n 105<\/div>\n 106<\/div>\n 107<\/div>\n 108<\/div>\n 109<\/div>\n 110<\/div>\n 111<\/div>\n 112<\/div>\n 113<\/div>\n 114<\/div>\n 115<\/div>\n 116<\/div>\n 117<\/div>\n 118<\/div>\n 119<\/div>\n 120<\/div>\n 121<\/div>\n 122<\/div>\n 123<\/div>\n 124<\/div>\n 125<\/div>\n 126<\/div>\n 127<\/div>\n 128<\/div>\n 129<\/div>\n 130<\/div>\n 131<\/div>\n 132<\/div>\n 133<\/div>\n 134<\/div>\n 135<\/div>\n 136<\/div>\n 137<\/div>\n 138<\/div>\n 139<\/div>\n 140<\/div>\n 141<\/div>\n 142<\/div>\n 143<\/div>\n 144<\/div>\n 145<\/div>\n 146<\/div>\n 147<\/div>\n 148<\/div>\n 149<\/div>\n 150<\/div>\n 151<\/div>\n 152<\/div>\n 153<\/div>\n 154<\/div>\n 155<\/div>\n 156<\/div>\n 157<\/div>\n 158<\/div>\n 159<\/div>\n 160<\/div>\n 161<\/div>\n 162<\/div>\n 163<\/div>\n 164<\/div>\n 165<\/div>\n 166<\/div>\n 167<\/div>\n 168<\/div>\n 169<\/div>\n 170<\/div>\n 171<\/div>\n 172<\/div>\n 173<\/div>\n 174<\/div>\n 175<\/div>\n 176<\/div>\n 177<\/div>\n 178<\/div>\n 179<\/div>\n 180<\/div>\n 181<\/div>\n 182<\/div>\n 183<\/div>\n 184<\/div>\n 185<\/div>\n 186<\/div>\n 187<\/div>\n 188<\/div>\n 189<\/div>\n 190<\/div>\n 191<\/div>\n 192<\/div>\n 193<\/div>\n 194<\/div>\n 195<\/div>\n 196<\/div>\n 197<\/div>\n 198<\/div>\n 199<\/div>\n 200<\/div>\n 201<\/div>\n 202<\/div>\n 203<\/div>\n 204<\/div>\n 205<\/div>\n 206<\/div>\n 207<\/div>\n 208<\/div>\n 209<\/div>\n 210<\/div>\n 211<\/div>\n<\/td>\n \n\n using<\/code> System;<\/code><\/div>\nusing<\/code>
| |
![\"\"](\"https:\/\/cn.hostease.com\/xueyuan\/wp-content\/uploads\/2017\/04\/gaixu.png\")
<\/a><\/figure>\n\n\n\n