sorry，l meet some problem，can you help me? #1
Comments
|
What is the start and end vertex of your graph? |
|
Has some edge with a negative value? |
|
some edge without a negative value. Thank you |
|
Do you need to visit all vertex? |
|
In Graph(example, 3, 129) the shortest path is [3, 2, 61, 140, 129] but in the Graph(example, 3, 19) the shortest path is [3, 2, 61, 140, 129, 136, 135, 128, 139, 138, 127, 134, 54, 53, 52, 51, 152, 155, 156, 60, 1, 0, 33, 26, 25, 24, 57, 58, 160, 154, 153, 115, 15, 9, 8, 14, 95, 38, 114, 113, 112, 10, 11, 12, 13, 7, 37, 73, 91, 92, 36, 35, 104, 105, 106, 107, 18, 76, 75, 74] with error in 74 vertex. The problem is the vertex weights. Always that you cross the vertex 74, the system don't know where it should go because all neighbors were already visited. Exemple Vertex 74 neighbors 105, 75, 12 and 37 |
|
Check the images |
|
Thank everyone，l have solved the problem but l used matlab.but i thank you for your care |
|
So, what was the solution? |
|
please see this code in the matlab. https://github.com/jl-wunder/-- |
I am doing a math modeling to optimize the public traffic.l need a program to solve the problem of the shortest route.but I am freshman so that l can't understand the dijkstra.finally，I find your program.I think it is very good.thank you.
when i modify the program，usually program will meet the problem
for vertex in self.shortest_path():
File "C:\Users\Administrator\Downloads\dijkstra-master\dijkstra-master\dijkstra.py", line 51, in shortest_path
back = self.P[back]
KeyError: -1
what is the trouble？
in exemple_1.py ,my dict example is
{0: {1: 760, 59: 779, 33: 403}, 1: {0: 760, 2: 930, 60: 368}, 2: {1: 930, 3: 305, 61: 400, 129: 539}, 3: {136: 416, 2: 305, 4: 2000}, 4: {3: 2000, 5: 700, 150: 346}, 5: {161: 2411, 4: 700, 6: 922}, 6: {20: 651, 5: 922, 21: 274}, 7: {8: 437, 13: 359, 37: 561}, 8: {9: 490, 7: 437, 14: 364, 73: 557}, 9: {8: 490, 72: 561, 15: 364}, 10: {112: 956, 11: 495, 76: 919}, 11: {113: 849, 10: 495, 75: 923, 12: 317}, 12: {114: 789, 11: 317, 74: 913, 13: 586}, 13: {12: 586, 14: 431, 38: 666, 7: 359}, 14: {8: 364, 15: 485, 13: 431, 95: 395}, 15: {9: 364, 115: 186, 14: 485}, 16: {17: 515, 109: 420, 78: 790}, 17: {16: 515, 18: 899, 108: 586, 77: 639}, 18: {17: 899, 107: 619, 76: 389}, 19: {64: 456, 122: 757, 20: 478}, 20: {19: 478, 6: 651, 62: 483}, 21: {6: 274, 22: 519, 150: 1466}, 22: {23: 522, 21: 519, 62: 458, 55: 1025}, 23: {22: 522, 54: 1006, 63: 465}, 24: {25: 483, 31: 783, 57: 495}, 25: {24: 483, 32: 673, 26: 538, 58: 540}, 26: {40: 541, 25: 538, 33: 422}, 27: {28: 402, 146: 2329, 44: 1297}, 28: {27: 402, 29: 580, 45: 1129}, 29: {28: 580, 30: 347, 46: 908}, 30: {34: 1481, 29: 347, 31: 520}, 31: {24: 783, 32: 468, 30: 520}, 32: {25: 673, 31: 468, 33: 765}, 33: {0: 403, 32: 765, 26: 422}, 34: {56: 319, 30: 1481, 39: 521}, 35: {104: 394, 36: 428, 94: 463}, 36: {35: 428, 92: 235, 37: 507}, 37: {73: 433, 74: 645, 36: 507, 7: 561}, 38: {114: 546, 39: 1098, 13: 666, 95: 632}, 39: {96: 511, 34: 521, 125: 365, 38: 1098}, 40: {41: 519, 26: 541, 59: 534, 58: 527}, 41: {40: 519, 96: 1012, 42: 521, 149: 525}, 42: {41: 521, 154: 552, 43: 496, 148: 530}, 43: {153: 558, 42: 496, 147: 535}, 44: {27: 1297, 45: 515, 47: 323}, 45: {48: 327, 28: 1129, 44: 515, 46: 531}, 46: {49: 327, 29: 908, 45: 531}, 47: {48: 509, 145: 624, 44: 323}, 48: {49: 534, 45: 327, 142: 618, 47: 509}, 49: {48: 534, 56: 380, 46: 327}, 50: {51: 576, 147: 448, 118: 514}, 51: {152: 450, 50: 576, 52: 517, 119: 880}, 52: {120: 1217, 138: 451, 51: 517, 53: 343}, 53: {121: 1415, 52: 343, 54: 348, 127: 451}, 54: {23: 1006, 53: 348, 134: 450, 55: 517}, 55: {22: 1025, 54: 517, 151: 443}, 56: {49: 380, 34: 319, 125: 400, 57: 799}, 57: {24: 495, 56: 799, 58: 487, 96: 523}, 58: {40: 527, 25: 540, 160: 519, 57: 487}, 59: {0: 779, 40: 534, 60: 573, 149: 519}, 60: {1: 368, 59: 573, 156: 528, 61: 530}, 61: {60: 530, 2: 400, 140: 522}, 62: {20: 483, 22: 458, 63: 513}, 63: {122: 202, 62: 513, 23: 465}, 64: {65: 567, 19: 456, 97: 1345}, 65: {64: 567, 66: 514, 83: 431, 122: 454}, 66: {65: 514, 67: 341, 84: 435, 121: 497}, 67: {120: 539, 66: 341, 68: 441, 85: 432}, 68: {67: 441, 69: 459, 86: 456, 119: 626}, 69: {68: 459, 70: 477, 118: 779, 87: 510}, 70: {88: 507, 71: 364, 117: 858, 69: 477}, 71: {72: 181, 89: 512, 116: 946, 70: 364}, 72: {9: 561, 90: 511, 71: 181, 73: 535}, 73: {8: 557, 72: 535, 91: 511, 37: 433}, 74: {105: 912, 75: 319, 12: 913, 37: 645}, 75: {74: 319, 11: 923, 76: 495, 106: 951}, 76: {10: 919, 75: 495, 18: 389, 77: 923}, 77: {17: 639, 76: 923, 78: 549, 111: 1861}, 78: {16: 790, 77: 549, 110: 1882}, 79: {80: 330, 98: 565, 126: 324}, 80: {81: 317, 99: 551, 132: 380, 79: 330}, 81: {80: 317, 82: 241, 131: 373, 100: 559}, 82: {81: 241, 130: 402, 101: 552}, 83: {65: 431, 84: 547, 97: 872}, 84: {98: 877, 83: 547, 66: 435, 85: 328}, 85: {67: 432, 99: 875, 84: 328, 86: 319}, 86: {68: 456, 100: 872, 85: 319, 87: 317}, 87: {88: 485, 69: 510, 86: 317, 101: 874}, 88: {89: 352, 70: 507, 102: 759, 87: 485}, 89: {88: 352, 90: 194, 71: 512}, 90: {72: 511, 89: 194, 91: 533, 103: 631}, 91: {73: 511, 90: 533, 92: 194, 94: 528}, 92: {91: 194, 36: 235}, 93: {130: 532, 123: 807, 94: 1139}, 94: {35: 463, 91: 528, 93: 1139, 103: 500}, 95: {96: 1352, 115: 401, 14: 395, 38: 632}, 96: {41: 1012, 39: 511, 57: 523, 95: 1352}, 97: {64: 1345, 98: 577, 83: 872, 133: 925}, 98: {97: 577, 99: 329, 84: 877, 79: 565}, 99: {80: 551, 98: 329, 100: 318, 85: 875}, 100: {81: 559, 99: 318, 101: 247, 86: 872}, 101: {82: 552, 100: 247, 102: 356, 87: 874}, 102: {88: 759, 101: 356, 103: 382}, 103: {90: 631, 94: 500, 102: 382, 130: 1029}, 104: {105: 317, 123: 1346, 35: 394}, 105: {104: 317, 74: 912, 124: 1345, 106: 319}, 106: {105: 319, 75: 951, 107: 387, 141: 1333}, 107: {144: 1310, 18: 619, 108: 968, 106: 387}, 108: {17: 586, 107: 968, 109: 548}, 109: {16: 420, 108: 548}, 110: {78: 1882, 111: 517}, 111: {112: 1029, 77: 1861, 110: 517}, 112: {145: 1098, 10: 956, 111: 1029, 113: 406}, 113: {112: 406, 114: 327, 11: 849, 142: 1188}, 114: {113: 327, 12: 789, 125: 1112, 38: 546}, 115: {153: 495, 15: 186, 116: 373, 95: 401}, 116: {115: 373, 117: 380, 71: 946}, 117: {116: 380, 70: 858, 118: 426}, 118: {50: 514, 117: 426, 69: 779, 119: 682}, 119: {120: 616, 51: 880, 68: 626, 118: 682}, 120: {121: 360, 67: 539, 52: 1217, 119: 616}, 121: {120: 360, 66: 497, 122: 477, 53: 1415}, 122: {65: 454, 19: 757, 63: 202, 121: 477}, 123: {104: 1346, 124: 325, 93: 807}, 124: {105: 1345, 123: 325, 141: 244}, 125: {56: 400, 114: 1112, 142: 505, 39: 365}, 126: {132: 332, 133: 561, 79: 324}, 127: {128: 498, 138: 347, 53: 451, 134: 350}, 128: {127: 498, 129: 518, 139: 348, 135: 352}, 129: {128: 518, 136: 356, 2: 539, 140: 340}, 130: {103: 1029, 82: 402, 131: 430, 93: 532, 159: 353}, 131: {81: 373, 130: 430, 132: 327, 159: 365}, 132: {80: 380, 137: 651, 131: 327, 126: 332}, 133: {97: 925, 126: 561}, 134: {127: 350, 151: 524, 54: 450, 135: 500}, 135: {128: 352, 136: 517, 134: 500, 151: 723}, 136: {129: 356, 3: 416, 150: 1460, 135: 517}, 137: {132: 651, 158: 490, 159: 332}, 138: {152: 511, 139: 497, 52: 451, 127: 347}, 139: {128: 348, 138: 497, 155: 509, 140: 521}, 140: {129: 340, 139: 521, 156: 513, 61: 522}, 141: {144: 318, 106: 1333, 124: 244}, 142: {48: 618, 113: 1188, 125: 505, 145: 439}, 143: {144: 2106}, 144: {107: 1310, 141: 318, 143: 2106}, 145: {112: 1098, 142: 439, 47: 624}, 146: {27: 2329}, 147: {152: 578, 50: 448, 43: 535, 148: 500}, 148: {42: 530, 147: 500, 155: 581, 149: 520}, 149: {41: 525, 148: 520, 59: 519, 156: 585}, 150: {136: 1460, 4: 346, 21: 1466, 151: 522}, 151: {55: 443, 134: 524, 150: 522, 135: 723}, 152: {138: 511, 51: 450, 147: 578, 155: 497}, 153: {43: 558, 154: 494, 115: 495}, 154: {160: 522, 153: 494, 42: 552}, 155: {152: 497, 148: 581, 139: 509, 156: 520}, 156: {60: 528, 155: 520, 140: 513, 149: 585}, 157: {158: 976}, 158: {137: 490, 157: 976}, 159: {137: 332, 130: 353, 131: 365}, 160: {58: 519, 154: 522}, 161: {5: 2411}}
if you help me,l will think you very much
The text was updated successfully, but these errors were encountered: